Finde die kleinste Zahl s < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Finde die kleinste Zahl s>0, sodass
[mm] 10^2\equiv [/mm] 1 (mod 17).
Was erfährt man dadurch über die Dezimalentwicklung? |
Hi,
zu dieser Aufgabe habe ich wieder folgende Lösung.
17 ist eine Primzahl und es gilt [mm] \phi(17)=16.
[/mm]
Mit Euler-Fermat folgt dann:
[mm] 10^{16}\equiv [/mm] 1 (mod 17).
Jetzt bleibt noch zu prüfen, ob 16 wirklich die kleinste Zahl ist.
[Bis hierher habe ich alles verstanden, der Teil, der folgt, den aber nicht]
10 [mm] \equiv [/mm] 10 (mod 17 )
10 · 10 [mm] \equiv [/mm] 100 (mod 17 ) [mm] \equiv [/mm] −2 (mod 31 )
10 · (−2) [mm] \equiv−20 [/mm] (mod 17 ) [mm] \equiv [/mm] −3 (mod 31 )
10 · (−3) [mm] \equiv [/mm] −30 (mod 17 ) [mm] \equiv [/mm] 4 (mod 31 )
10 · 4 [mm] \equiv40 [/mm] (mod 17 ) [mm] \equiv [/mm] 6 (mod 31 )
10 · 6 [mm] \equiv [/mm] 60 (mod 17 ) [mm] \equiv [/mm] −8 (mod 31 )
10 · (−8) [mm] \equiv [/mm] −80 (mod 17 ) [mm] \equiv [/mm] 5 (mod 31 )
10 · 5 [mm] \equiv [/mm] 50 (mod 17 ) [mm] \equiv [/mm] −1 (mod 31 )
Nun wiederholt sich auf Grund der −1 bei 108 alle mit umgekehrten Vorzeichen und wir erkennen daher, dass s = 16 wirklich die kleinste Zahl mit der gegebenen Bedingung ist.
Also
> 10 [mm] \equiv [/mm] 10 (mod 17 )
Das ist auch klar, wenn ich 10:17 rechne, bleibt Rest 10
> 10 · 10 [mm] \equiv [/mm] 100 (mod 17 ) [mm] \equiv [/mm] −2 (mod 31 )
hier fängts schon an, wenn ich 100:17 teile, dann bekomme ich doch 5 Rest 15, wieso schreiben die aber [mm] \equiv [/mm] 100
andere Frage, wie kommen die von 100 (mod 17) auf [mm] \equiv [/mm] −2 (mod 31), welche Regel wird hier angewendet??
> 10 · (−2) [mm] \equiv−20 [/mm] (mod 17 ) [mm] \equiv [/mm] −3 (mod 31)
Wieso rechnen die hier auf einmal mal (-2)?? ich dachte jetzt, dass wir nur die Zahlen s=1-16 betrachten müssen??
könnt ihr mir dieses Vorgehen vielleicht nochmal erklären??
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:57 Di 31.05.2011 | | Autor: | abakus |
> Finde die kleinste Zahl s>0, sodass
>
> [mm]10^2\equiv[/mm] 1 (mod 17).
>
> Was erfährt man dadurch über die Dezimalentwicklung?
> Hi,
>
> zu dieser Aufgabe habe ich wieder folgende Lösung.
>
> 17 ist eine Primzahl und es gilt [mm]\phi(17)=16.[/mm]
>
> Mit Euler-Fermat folgt dann:
>
> [mm]10^{16}\equiv[/mm] 1 (mod 17).
>
> Jetzt bleibt noch zu prüfen, ob 16 wirklich die kleinste
> Zahl ist.
>
> [Bis hierher habe ich alles verstanden, der Teil, der
> folgt, den aber nicht]
>
> 10 [mm]\equiv[/mm] 10 (mod 17 )
> 10 · 10 [mm]\equiv[/mm] 100 (mod 17 ) [mm]\equiv[/mm] −2 (mod 31 )
> 10 · (−2) [mm]\equiv−20[/mm] (mod 17 ) [mm]\equiv[/mm] −3 (mod 31 )
> 10 · (−3) [mm]\equiv[/mm] −30 (mod 17 ) [mm]\equiv[/mm] 4 (mod 31 )
> 10 · 4 [mm]\equiv40[/mm] (mod 17 ) [mm]\equiv[/mm] 6 (mod 31 )
> 10 · 6 [mm]\equiv[/mm] 60 (mod 17 ) [mm]\equiv[/mm] −8 (mod 31 )
> 10 · (−8) [mm]\equiv[/mm] −80 (mod 17 ) [mm]\equiv[/mm] 5 (mod 31 )
> 10 · 5 [mm]\equiv[/mm] 50 (mod 17 ) [mm]\equiv[/mm] −1 (mod 31 )
>
> Nun wiederholt sich auf Grund der −1 bei 108 alle mit
> umgekehrten Vorzeichen und wir erkennen daher, dass s = 16
> wirklich die kleinste Zahl mit der gegebenen Bedingung
> ist.
>
> Also
>
> > 10 [mm]\equiv[/mm] 10 (mod 17 )
>
> Das ist auch klar, wenn ich 10:17 rechne, bleibt Rest 10
>
> > 10 · 10 [mm]\equiv[/mm] 100 (mod 17 ) [mm]\equiv[/mm] −2 (mod 31 )
>
> hier fängts schon an, wenn ich 100:17 teile, dann bekomme
> ich doch 5 Rest 15, wieso schreiben die aber [mm]\equiv[/mm] 100
Nein. Sie schreiben [mm]\equiv[/mm] -2
und das stimmt, denn die Differenz aus 100 und -2 ist 102 (was durch 17 teilbar ist).
Es gilt -2[mm]\equiv[/mm] 15[mm]\equiv[/mm] 32[mm]\equiv[/mm] 49[mm]\equiv[/mm] 66[mm]\equiv[/mm] 83[mm]\equiv[/mm] 100 mod 17.
>
> andere Frage, wie kommen die von 100 (mod 17) auf [mm]\equiv[/mm]
> −2 (mod 31), welche Regel wird hier angewendet??
Gar keine. Das "mod 31" gehört hier nicht hin, es muss nach wie vor (auch in den nächsten Zeilen) mod 17 heißen.
>
> > 10 · (−2) [mm]\equiv−20[/mm] (mod 17 ) [mm]\equiv[/mm] −3 (mod 31)
>
> Wieso rechnen die hier auf einmal mal (-2)?? ich dachte
> jetzt, dass wir nur die Zahlen s=1-16 betrachten müssen??
>
> könnt ihr mir dieses Vorgehen vielleicht nochmal
> erklären??
>
> Danke
|
|
|
| |
|
HI,
> Gar keine. Das "mod 31" gehört hier nicht hin, es muss nach wie vor (auch in den nächsten Zeilen) mod 17 heißen.
D.h. die Lösung ist an dieser Stelle fehlerhaft? und es muss immer mod 17 heißen, richtig?
Ich verstehe trotzdem nicht, wie die einzelnen Zeilen zustanden kommen.
Die wollen ja prüfgen, ob
[mm] 10^{16}\equiv [/mm] 1 (mod 17) für s=16 das maximale ist. Aber wie gehen die bei der Prüfung hier vor???
> 10 · 10 $ [mm] \equiv [/mm] $ 100 (mod 17 ) $ [mm] \equiv [/mm] $ −2 (mod 17 )
> 10 · (−2) $ [mm] \equiv−20 [/mm] $ (mod 17 ) $ [mm] \equiv [/mm] $ −3 (mod 17 )
> 10 · (−3) $ [mm] \equiv [/mm] $ −30 (mod 17 ) $ [mm] \equiv [/mm] $ 4 (mod 17 )
Wie kommen dann diese Zeilen zustande? Sind die so überhaupt richtig?
Und außerdem dachte ich, dass man jetzt
[mm] 10^1
[/mm]
[mm] 10^2
[/mm]
... bis
[mm] 10^{16}
[/mm]
überprüfen muss?? also
[mm] 10^1 [/mm] = 10 [mm] \equiv [/mm] 10 (mod 17)
[mm] 10^2 [/mm] = 100 [mm] \equiv [/mm] 15 (mod 17)
[mm] 10^3 [/mm] = 1000 [mm] \equiv [/mm] 4 (mod 17)
Aber das wird ja für immer größer werdende Potenzen nicht so einfach zu rechnen. und außerdem bekommt man ja irgendwie den bezug zu [mm] 10^s \equiv [/mm] 1 (mod 17)
deswegen will ich schon gerne verstehen, was die dort gerechnet haben.
grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:57 Di 31.05.2011 | | Autor: | Fulla |
Hallo jaruleking,
> HI,
>
> > Gar keine. Das "mod 31" gehört hier nicht hin, es muss
> nach wie vor (auch in den nächsten Zeilen) mod 17 heißen.
>
> D.h. die Lösung ist an dieser Stelle fehlerhaft? und es
> muss immer mod 17 heißen, richtig?
Ja, genau.
> Ich verstehe trotzdem nicht, wie die einzelnen Zeilen
> zustanden kommen.
>
> Die wollen ja prüfgen, ob
>
> [mm]10^{16}\equiv[/mm] 1 (mod 17) für s=16 das maximale ist. Aber
> wie gehen die bei der Prüfung hier vor???
>
> > 10 · 10 [mm]\equiv[/mm] 100 (mod 17 ) [mm]\equiv[/mm] −2 (mod 17 )
> > 10 · (−2) [mm]\equiv−20[/mm] (mod 17 ) [mm]\equiv[/mm] −3 (mod 17
> )
> > 10 · (−3) [mm]\equiv[/mm] −30 (mod 17 ) [mm]\equiv[/mm] 4 (mod 17 )
>
> Wie kommen dann diese Zeilen zustande? Sind die so
> überhaupt richtig?
>
> Und außerdem dachte ich, dass man jetzt
>
> [mm]10^1[/mm]
> [mm]10^2[/mm]
> ... bis
> [mm]10^{16}[/mm]
>
> überprüfen muss?? also
>
> [mm]10^1[/mm] = 10 [mm]\equiv[/mm] 10 (mod 17)
> [mm]10^2[/mm] = 100 [mm]\equiv[/mm] 15 (mod 17)
> [mm]10^3[/mm] = 1000 [mm]\equiv[/mm] 4 (mod 17)
>
> Aber das wird ja für immer größer werdende Potenzen
> nicht so einfach zu rechnen. und außerdem bekommt man ja
> irgendwie den bezug zu [mm]10^s \equiv[/mm] 1 (mod 17)
>
> deswegen will ich schon gerne verstehen, was die dort
> gerechnet haben.
>
> grüße
Es wird hier auch nichts anderes gemacht, als die Potenzen [mm]10^1[/mm] bis [mm]10^{16}[/mm] mod 17 zu betrachten:
Bei den ersten zwei Zeilen sind wir uns noch einig:
[mm]10^1\equiv 10\mod 17[/mm]
[mm]10^2=100\equiv 15 \mod 17\equiv -2\mod 17[/mm]
In den folgenden Zeilen wird jeweils das Ergebnis der Vorangegangenen verwendet:
[mm]10^3=10*10^2\equiv 10*(-2)\mod 17\equiv -20\mod 17\equiv -3\mod 17 (\equiv 14\mod 17)[/mm]
[mm]10^4=10*10^3\equiv 10*(-3)\mod 17 \equiv -30\mod 17\equiv 4\mod 17[/mm]
usw.
So findest du dann dass [mm]10^8\equiv -1\mod 17[/mm], also ist
[mm]10^9\equiv -10 \mod 17[/mm]
[mm]10^{10}\equiv -100\mod 17 \equiv 2\mod 17[/mm]
etc. Also mit umgekehrtem Vorzeichen wie oben. Daher ist [mm]10^{16}[/mm] die kleinste Potenz für die [mm]\equiv 1\mod 17[/mm] gilt.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:07 Di 31.05.2011 | | Autor: | jaruleking |
Hi,
vielen Dank für deine ganz ausführliche Erklärung. Jetzt habe ich es auch verstanden 
Grüße
|
|
|
|
