Dezimaldarstellung nur 0 und 1 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:09 Fr 04.08.2006 | | Autor: | VerenaB |
| Aufgabe | Zu zeigen ist: Für eine beliebige natürliche Zahl m gilt:
Es gibt unendlich viele [mm] $n\in\IN$, [/mm] die in ihrer Dezimaldarstellung nur aus Nullen und Einsen bestehen und Vielfache von m sind. |
Hallo,
Ich hab mir überlegt, dass ich nur die Existenz von einer solchen Zahl zeigen muss, weil dann ja auf jeden Fall alle 10,100, 1000 fachen dieser Zahl dann auch nur aus 0 und 1 bestehen und durch m teilbar sind.
ich hab mir überlegt, ob man hier irgendwie über die Dezimalbruchdarstellung argumentieren kann, die ja eindeutig ist. Weiß aber nicht, wie...
Außerdem hab ich mir einen Algorithmus überlegt, wie man eine solche Zahl finden kann:
Sei m in Dezimaldarstellung gleich T H Z E.
Dann suche einstellige Zahl a, so dass a*E=0 mod 10 oder 0 mod 11.
Bilde $a*m$. Nun betrachte die vorletzte Stelle von $a*m$.
Nun suche $b$, so dass für die letzte Stelle von b*m genau $-a mod 10$ oder -a mod 11.
Dann betrachte $ba*m$, und davon die vorvorletzte Ziffer und verfahre analog...
Beispiel: 7
7*3=21, 1=0 mod 11
7*4=28, 8=-2 mod 10
7*43=301
7*1=7=-3 mod 10
7*143=1001
Jetzt weiß ich jedoch nicht, wie ich beweisen kann, dass dieser Algorithmus immer funktioniert und auch mal abbricht...
Vielleicht fehlt mir auch irgendein Satz, mit dem obige Aussage relativ einfach zeigen kann.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:18 Fr 04.08.2006 | | Autor: | DirkG |
Betrachte erstmal nur die $m$, die in ihrer Primfaktordarstellung weder 2 noch 5 enthalten - diese Einschränkung macht kein Problem, wenn man am Ende genügend Nullen dranhängt.
Und dann denke an den Satz von Euler-Fermat, angewandt auf das Modul $9m$:
Es ist [mm] $10^{\varphi(9m)}\equiv 1\mod [/mm] (9m)$, umgeschrieben [mm] $\frac{10^{\varphi(9m)}-1}{9}\equiv 0\mod [/mm] m$. Links steht die Zahl, die aus genau [mm] $\varphi(9m)$ [/mm] Einsen besteht.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:26 Fr 04.08.2006 | | Autor: | statler |
Hallo Verena!
> Zu zeigen ist: Für eine beliebige natürliche Zahl m gilt:
> Es gibt unendlich viele [mm]n \in \IN[/mm], die in ihrer
> Dezimaldarstellung nur aus Nullen und Einsen bestehen und
> Vielfache von m sind.
> Ich hab mir überlegt, dass ich nur die Existenz von einer
> solchen Zahl zeigen muss, weil dann ja auf jeden Fall alle
> 10,100, 1000 fachen dieser Zahl dann auch nur aus 0 und 1
> bestehen und durch m teilbar sind.
OK
Fangen wir mal mit einem m an, was zu 10 teilerfremd ist. Dann gibt es ein Vielfaches von m, das nur aus 1en besteht. Das kann ich so einsehen:
Ich schreibe mir alle Zahlen 1, 11, 111, 1111 usw. bis m 1en auf und teile sie durch m mit Rest. Wenn das bei einer Zahl aufgeht, bin ich fertig. Andernfalls lassen 2 den gleichen Rest (nach dem Schubfachprinzip). Dann sieht die Differenz dieser beiden so aus: 11...110...0. Aber wenn m zu 10 teilerfremd ist, teilt es schon die Zahl, die aus den ersten 1en besteht. Also gibt es für den Fall (m, 10) = 1 so ein Vielfaches.
Wenn m Vielfaches von 10 ist, also Nullen am Ende hat, so spielt das keine Rolle, weil die bei jedem Vielfachen wieder auftaucchen und erlaubt sind. Ich kann also annehmen, daß m nicht auf 0 endet. Dann steckt in m evtl. noch eine 2er- oder 5er-Potenz. Aber damit werden wir fertig.
Wenn m' der zu 10 teilerfremde Teil ist und rm' = 1...1 gelöst ist, dann ist (2r)(5m') = 1....10 und (5r)(2m') = 1...10.
Also ist der Lösungsweg klar:
Schreibe m = [mm] 10^{s}*5^{t}*2^{u}*m' [/mm] mit (10, m') = 1, s, t, u [mm] \ge [/mm] 0, t = 0 oder u = 0
Löse dann r*m' = 1...1
Falls z. B. u = 0, setze r' = [mm] 2^{t}*r
[/mm]
Dann ist
r'*m = [mm] 2^{t}*r*10^{s}*5^{t}*2^{0}*m' [/mm]
= [mm] 10^{s+t}*r*m' [/mm] = 1...10.....0
wie gewünscht.
Ich bitte um Nachprüfung!
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:45 Fr 04.08.2006 | | Autor: | DirkG |
Genau genommen reicht folgender Extrakt aus deinem Beitrag als Beweis für alle (!) $m$:
> Ich schreibe mir alle Zahlen 1, 11, 111, 1111 usw. bis m
> 1en auf und teile sie durch m mit Rest. Wenn das bei einer
> Zahl aufgeht, bin ich fertig. Andernfalls lassen 2 den
> gleichen Rest (nach dem Schubfachprinzip). Dann sieht die
> Differenz dieser beiden so aus: 11...110...0.
Das war's schon, denn diese Differenz hat die geforderte Gestalt und ist durch $m$ teilbar. Schöner, kurzer und auch einfacher Beweis, kommt im Gegensatz zu meinem ohne Eulersche Phi-Funktion aus. ![[ok]](/images/smileys/ok.gif "[ok]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:53 Sa 05.08.2006 | | Autor: | VerenaB |
Hallo Dieter und Dirk,
vielen Dank für Eure Ideen, sie haben mir sehr geholfen...
LG,
Verena
|
|
|
|
