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..