Teilbarkeit. Beweis: Rm|Rn wenn m|n

Question

Hi,

Ich möchte zeigen, dass die Repunit R_n genau dann durch R_m teilbar ist, wenn m|n.

$${R}_{n}=\frac{{10}^{n}-1}{9}$$

mit n∈ℕ.

Nun habe ich versucht es zu beweisen, bin mir aber unsicher ob der Beweis richtig und in sich logisch und schlüssig ist:

$$\frac { { 10 }^{ n }-1 }{ 9 } \equiv 0\quad mod\quad \frac { { 10 }^{ m }-1 }{ 9 } \quad \\ Aus\quad { R }_{ m }|{ R }_{ n }\quad folgt\quad 9{ R }_{ m }|9{ R }_{ n }\\ \Rightarrow { 10 }^{ n }-1\equiv 0\quad mod\quad { 10 }^{ m }-1\\ \Rightarrow { 10 }^{ n }\equiv 1\quad mod\quad { 10 }^{ m }-1\\ Da\quad m|n\\ { ({ 10 }^{ m }) }^{ k }\equiv 1\quad mod\quad { 10 }^{ m }-1\quad mit\quad k=\frac { n }{ m } \\ Aus\quad x*y\quad mod\quad p\quad =\quad [x\quad mod\quad p\quad *\quad y\quad mod\quad p]\quad mod\quad p\\ und\quad { 10 }^{ m }-1\equiv 0\quad mod\quad { 10 }^{ m }-1\quad und\quad damit\quad auch\quad { 10 }^{ m }\equiv 1\quad mod\quad { 10 }^{ m }-1\quad folgt:\\ 1^{ k }\equiv 1\quad mod\quad { 10 }^{ m }-1$$

Wäre nett wenn sich das jemand mit mehr Erfahrung in diesem Bereich anschauen könnte ^^

Gruß
EmNero

Answer 1

Hallo EmNero,

der Beweis hat ein paar schwerwiegende Probleme.

1) Zeigst du nicht, dass aus dem einen das andere folgt sondern benutzt irgendwie gleichzeitig, dass $R_m|R_n$ und $m|n$ gilt. Somit verlierst du schon mal das Ziel aus den Augen.

2) $10^m-1$ ist nicht unbedingt eine Primzahl.

Hier mal ein Vorschlag für den Beweis (bin bisschen eingerostet, deswegen ist das ganze eventuell ziemlich unelegant).

I) Wenn $m|n$ gilt, also $n = km$ für ein $k\in \mathbb{N}$, dann substituiere (zur besseren Verständlichkeit) $10^m=z$.

Dann hast du $(z^k-1) = (z-1) \sum \limits_{i=0}^{k-1}z^i$ und somit $R_m|R_n$.

II) Nehmen wir an, dass $R_m|R_n$ gilt, was bedeutet, dass  $10^m-1|10^n-1$.

Außerdem nehmen wir an, dass $m \nmid n$, was bedeutet, dass $a,b \in \mathbb{N}$ existieren mit $n=am+b$ und $0 < b <m$.

Betrachte nun:

$$10^n-1 = 10^{am+b}-1 = 10^b \cdot 10^{am} -1 = 10^b \cdot 10^{am} - 10^b + 10^b -1 \\ = 10^b(10^{am}-1)+(10^b-1)$$

Nach I) gilt $10^m-1 | 10^{am}-1$, allerdings erhalten wir durch $10^m-1 \nmid 10^b-1$ den Widerspruch zu $10^m-1|10^n-1$. Somit muss also $m |n$ gelten.

Gruß

Comments

Hi,

ich dachte in könnte die beiden Behauptungen verwenden und sie durch Umformung auf ein allgemein gültiges Ergebnis (nämlich 1^k kongruent 1 modulo (10^m)-1) bringen. Zeigt das nicht, dass beide Behauptungen wahr sein müssen? Sonst könnte ja am Ende kein wahres Ergebnis bei rauskommen, oder? Vielleicht vertue ich mich hierbei auch :D

Warum sollte 10^m-1 eine Primzahl sein?

Deine Vorschläge in 2 muss ich mir mal in Ruhe anschauen.

Wikipedia meint es ist leicht zu zeigen, mehr dann aber auch nicht...

Für a<b

$${ R }_{ ab }={ 10 }^{ a(b-1) }{ R }_{ a }+{ 10 }^{ a(b-2) }{ R }_{ a }+{ { 10 }^{ a(b-3) }R }_{ a }+...+{ { 10 }^{ a(b-(b-2)) }R }_{ a }+{ { 10 }^{ a(b-(b-1)) }R }_{ a }+{ R }_{ a }$$

Wäre ja dann durch Ra teilbar...

Gruß

---

Nein, dann zeigst du nicht die Äquivalenz $A \Leftrightarrow B$ sondern, dass aus A und B irgendwas neues C folgt.

Weil $10^m-1$ offensichtlich durch 9 teilbar ist ;) für $m \geq 1$

Das was du danach geschrieben hast steht bei mir unter I).

---

Nun ja ich habe doch aber nie behauptet, dass es eine Primzahl ist. Hmmm ich muss da erstmal wieder drüber nachdenken :D

---

Ah ok, war durch das $p$ irritiert, aber stimmt das mit dem Produkt ist nicht auf Primzahlen beschränkt.

---

Was ist wenn ich den Beweis anders aufbaue:

$$m|n\quad =>\quad k*m=n\\ \frac { { 10 }^{ n }-1 }{ 9 } \equiv x\quad mod\quad \frac { { 10 }^{ m }-1 }{ 9 } \\ \left( \frac { { 10 }^{ n }-1 }{ 9 } =t*\frac { { 10 }^{ m }-1 }{ 9 } +x\quad |*9\\ { 10 }^{ n }-1=t*{ 10 }^{ m }-1+9x \right) \\ { 10 }^{ n }-1\equiv 9x\quad mod\quad { 10 }^{ m }-1\\ { 10 }^{ n }\equiv 9x+1\quad mod\quad { 10 }^{ m }-1\\ { 10 }^{ km }\equiv 9x+1\quad mod\quad { 10 }^{ m }-1\\ Leicht\quad zu\quad zeigen:\\ { 10 }^{ m }\equiv 1\quad mod\quad { 10 }^{ m }-1\\ { 1 }^{ k }\equiv 9x+1\quad mod\quad { 10 }^{ m }-1\\ { 1 }^{ k }-1\equiv 9x\quad mod\quad { 10 }^{ m }-1\\ 0\equiv 9x\quad mod\quad { 10 }^{ m }-1\\ \Rightarrow x=0\\ \Rightarrow \frac { { 10 }^{ n }-1 }{ 9 } \equiv 0\quad mod\quad \frac { { 10 }^{ m }-1 }{ 9 } \\ etc.$$

Wenn das immer noch falsch ist probiere ich eben den anderen Weg :D

---

Ach sorry ich hatte dich ganz vergessen. Hoffe das kommt nicht allzu spät

 Sieht gut aus. ;)

---

Zu spät kommt es auf keinen Fall, war ja nur eine Frage aus eigenem Interesse.

Aufjedenfall Danke für die Rückmeldung ^^

Mir fällt aber auf, dass ich auch etwas vergessen habe..