Modulorechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige, dass für alle [mm] n\in\IZ n^9 \equiv [/mm] n (mod 30) gilt. |
Hi,
bei dieser Aufgabe habe ich mir das so gedacht. Wenn ich zeige, dass die Aussage für alle Primzahlen gilt, dann gilt es auch für alle [mm] n\in \IZ.
[/mm]
habe dann mal mit der 2 angefangen, also
[mm] 2^9 \equiv [/mm] 2 (mod 30) stimmt
[mm] 3^9 \equiv [/mm] 3 (mod 30) stimmt auch
also auch 2*6, ist [mm] 12^9 \equiv [/mm] 12 (mod 30)
Das müsste doch so gehen, oder?? Nur, wie kann ich das jetzt für alle Primzahlen zeigen?? Habt ihr da vielleicht eine Idee??
Grüße
|
|
| |
|
Hallo jaruleking,
> Zeige, dass für alle [mm]n\in\IZ n^9 \equiv[/mm] n (mod 30)
> gilt.
> Hi,
>
> bei dieser Aufgabe habe ich mir das so gedacht. Wenn ich
> zeige, dass die Aussage für alle Primzahlen gilt, dann
> gilt es auch für alle [mm]n\in \IZ.[/mm]
>
> habe dann mal mit der 2 angefangen, also
>
> [mm]2^9 \equiv[/mm] 2 (mod 30) stimmt
>
> [mm]3^9 \equiv[/mm] 3 (mod 30) stimmt auch
>
> also auch 2*6, ist [mm]12^9 \equiv[/mm] 12 (mod 30)
>
> Das müsste doch so gehen, oder?? Nur, wie kann ich das
> jetzt für alle Primzahlen zeigen?? Habt ihr da vielleicht
> eine Idee??
Na, für alle Primzahlen musst du das nicht zeigen, da hättest du auch viel zu tun!
Ich habe es jetzt noch nicht durchgerechnet, aber als Konzept folgendes:
Es ist [mm]30=2\cdot{}3\cdot{}5[/mm]
Zeige also, dass [mm]n^9 \ \equiv \ n \ \operatorname{mod}(2)[/mm] und [mm]n^9 \ \equiv \ n \ \operatorname{mod}(3)[/mm] und [mm]n^9 \ \equiv \ n \ \operatorname{mod}(5)[/mm] gilt.
Dazu kann es helfen, die Kongruenzen umzuschreiben in [mm]n^9-n \ \equiv \ 0 \ \operatorname{mod}(p_i)[/mm] bzw. [mm]n(n^8-1)=n(n-1)(n+1)(n^2+1)(n^4+1) \ \equiv \ 0 \ \operatorname{mod}(p_i)[/mm]
Da habe ich mehrfach die 3.binomische Formel angewendet.
Damit ist es für [mm]p=2,3[/mm] schon klar, denn die ersten 3 Faktoren sind 3 aufeinanderfolgende Zahlen (in falscher Reihenfolge zwar), und deren Produkt sind sicher durch [mm]2[/mm] und [mm]3[/mm] teilbar.
Bleibt nur der Nachweis: [mm]n^9 \ \equiv \ n \ \operatorname{mod}(5)[/mm] - in welcher Form auch immer ...
Gruß
schachuzipus
|
|
|
| |
|
Hallo jaruleking,
der Tipp von schachuzipus ist Gold wert, nur die Zerlegung von [mm] n^9-n [/mm] in Faktoren ist nicht nötig.
Es geht viel schneller, wenn Du den "kleinen Fermat" kennst:
für [mm] p\in\IP [/mm] ist für alle a mit ggT(a,p)=1 die Kongruenz [mm] a^{p-1}\equiv 1\mod{p} [/mm] erfüllt.
Außerdem gilt für a=kp immer [mm] a^m\equiv a\equiv 0\mod{p} [/mm] für alle [mm] m\in\IN\setminus\{0\}.
[/mm]
Damit kannst Du die drei Kongruenzen [mm] \mod{2}, \mod{3} [/mm] und [mm] \mod{5} [/mm] ja schnell erschlagen.
Übrigens ist [mm] \phi(30)=8. [/mm] Vielleicht klingelt da auch etwas?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:00 Sa 23.07.2011 | | Autor: | jaruleking |
ok,
danke euch für die tipps.
grüße
|
|
|
|
