Kongruenz mit mod p^2 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen sie, für jede Primzahl gilt:
[mm] 5^{p^2}\equiv 5^p [/mm] mod [mm] p^2 [/mm] |
Leider hab ich hier relativ wenige Ideen.
[mm] 5^{p^2} [/mm] = [mm] (5^p)^p
[/mm]
Also reicht es zu zeigen, dass
[mm] 5^p \equiv [/mm] 5 mod [mm] p^2 [/mm] ist...
denn wenn das gilt , gilt auch
[mm] 5^{p^2} \equiv (5^p)^p [/mm] mod [mm] p^2
[/mm]
richtig?
|
|
| |
|
Ok... ich glaube ich hab es...
Fall 1:
p [mm] \not= [/mm] 5 und p primzahl:
[mm] \phi(p^2)=p*(p-1)=p^2-p [/mm] (Satz 5.7)
Wir wissen: [mm] a^{\phi(m)} \equiv [/mm] 1 mod m (Satz 5.8)
also
[mm] a^p^2-p \equiv [/mm] 1 mod [mm] p^2
[/mm]
und da p nicht 5 und Primzahl ist, gilt dies auch für a=5
->
[mm] 5^{(p^2)-p} \equiv [/mm] 1 mod [mm] p^2
[/mm]
Wir wissen außerdem, dass wenn
a [mm] \equiv [/mm] b mod m
auch gilt a*c [mm] \equiv [/mm] b*c mod m (Korollar nach Satz 5.3)
sei [mm] c=5^p
[/mm]
[mm] 5^{(p^2)-p}*5^p=5^p^2 \equiv 1*5^p=5^p [/mm] mod [mm] p^2
[/mm]
Fall 2 p=5
da [mm] 25|25(5^23-5^3)
[/mm]
folgt [mm] 25|(25*5^23)-(25*5^3)
[/mm]
also [mm] 25|5^25-5^5
[/mm]
also [mm] 5^2|5^25-5^5
[/mm]
-> 5^25 [mm] \equiv 5^5 [/mm] mod [mm] 5^2 [/mm] (Def Kongurenz)
|
|
|
| |
|
Hallo Nadelspitze,
> Ok... ich glaube ich hab es...
>
> Fall 1:
> p [mm]\not=[/mm] 5 und p primzahl:
> [mm]\phi(p^2)=p*(p-1)=p^2-p[/mm] (Satz 5.7)
>
> Wir wissen: [mm]a^{\phi(m)} \equiv[/mm] 1 mod m (Satz 5.8)
> also
> [mm]a^p^2-p \equiv[/mm] 1 mod [mm]p^2[/mm]
>
> und da p nicht 5 und Primzahl ist, gilt dies auch für a=5
> ->
> [mm]5^{(p^2)-p} \equiv[/mm] 1 mod [mm]p^2[/mm]
> Wir wissen außerdem, dass wenn
> a [mm]\equiv[/mm] b mod m
> auch gilt a*c [mm]\equiv[/mm] b*c mod m (Korollar nach Satz 5.3)
> sei [mm]c=5^p[/mm]
> [mm]5^{(p^2)-p}*5^p=5^p^2 \equiv 1*5^p=5^p[/mm] mod [mm]p^2[/mm]![[ok]](/images/smileys/ok.gif "[ok]")
Schöner Beweis und gut begründet!
Vllt. solltest du noch ganz kurz erwähnen, wieso bzw. dass für [mm] $p\neq [/mm] 5$ und prim stets [mm] $\operatorname{ggT}(5,p^2)=1$ [/mm] ist ...
>
>
> Fall 2 p=5
>
> da [mm]25|25(5^23-5^3)[/mm]
> folgt [mm]25|(25*5^23)-(25*5^3)[/mm]
> also [mm]25|5^25-5^5[/mm]
> also [mm]5^2|5^25-5^5[/mm]
>
> -> 5^25 [mm]\equiv 5^5[/mm] mod [mm]5^2[/mm] (Def Kongurenz)
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:09 Mi 21.12.2011 | | Autor: | abakus |
> Beweisen sie, für jede Primzahl gilt:
> [mm]5^{p^2}\equiv 5^p[/mm] mod [mm]p^2[/mm]
>
> Leider hab ich hier relativ wenige Ideen.
>
>
> [mm]5^{p^2}[/mm] = [mm](5^p)^p[/mm]
>
> Also reicht es zu zeigen, dass
> [mm]5^p \equiv[/mm] 5 mod [mm]p^2[/mm] ist...
>
> denn wenn das gilt , gilt auch
> [mm]5^{p^2} \equiv (5^p)^p[/mm] mod [mm]p^2[/mm]
>
> richtig?
>
>
Hallo,
mit Sätzen zur Phi-Funktion bin ich nicht mehr so richtig fit, aber es geht wohl auch ohne.
Es gilt [mm]5^{p^2}\equiv 5^p mod p^2 \gdw 5^{p^2}- 5^p \equiv 0 mod p^2\gdw p^2 | 5^p(5^{p^2-p}-1})[/mm].
Letztendlich führt auch das wieder zu deiner Fallunterscheidung.
Gruß Abakus
|
|
|
| |
|
Hey abakus, vielen Dank für deine Antwort. Leider darf ich den Schritt, den du gepostet hast (noch) nicht benutzen. Dennoch danke, es ist immer wieder schön zu sehen, dass Aufgaben unterschiedlich gelöst werden können.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:19 Mi 21.12.2011 | | Autor: | abakus |
> Hey abakus, vielen Dank für deine Antwort. Leider darf ich
> den Schritt, den du gepostet hast (noch) nicht benutzen.
Echt nicht?
Dass man auf beiden Seiten einer Kongruenz Gleiches subtrahieren darf ist doch wesentlich elementarer als eine Phi-Funktion.
Die übrigen Schritte (Ausklammern eines Faktors und die Erkenntnis "Rest 0 bedeutet Teilbarkeit") sind Schulstoff.
Na ja, die Profs sind da manchmal etwas eigen...
Gruß Abakus
> Dennoch danke, es ist immer wieder schön zu sehen, dass
> Aufgaben unterschiedlich gelöst werden können.
>
>
|
|
|
| |
|
Hallo Nadelspitze,
Dein Beweis steht ja jetzt und ist fertig und richtig.
Trotzdem liegt in Deiner ersten Anfrage eine Falle verborgen, auf die ich Dich aufmerksam machen möchte, nur der Vollständigkeit halber.
> Beweisen sie, für jede Primzahl gilt:
> [mm]5^{p^2}\equiv 5^p[/mm] mod [mm]p^2[/mm]
>
> Leider hab ich hier relativ wenige Ideen.
>
> [mm]5^{p^2}[/mm] = [mm](5^p)^p[/mm]
>
> Also reicht es zu zeigen, dass
> [mm]5^p \equiv[/mm] 5 mod [mm]p^2[/mm] ist...
So bist Du ja auch vorgegangen, aber gerade hier liegt die Falle verborgen.
> denn wenn das gilt , gilt auch
> [mm]5^{p^2} \equiv (5^p)^p[/mm] mod [mm]p^2[/mm]
> richtig?
Stimmt schon. Aber auch wenn [mm] 5^p\not\equiv 5\mod{p^2} [/mm] gewesen wäre, hätte die zu zeigende Äquivalenz noch stimmen können.
Solange Dir das klar ist, ist an Deiner Vorgehensweise nichts auzusetzen. Du zeigst etwas anderes als das Geforderte und folgerst daraus, dass das zu Zeigende aus dem von Dir gezeigten folgt. Dieser Weg ist korrekt, aber eben nicht in der umgekehrten Richtung zu gehen.
Grüße
reverend
PS: Ein Beispiel, bei dem das nicht klappt, ist [mm] x^4\equiv 1\mod{35}. [/mm] Daraus folgt nicht [mm] x^2\equiv \pm 1\mod{35}. [/mm] Dabei würdest Du z.B. die Lösung [mm] x\equiv{8} [/mm] verlieren. Erst recht folgt nicht [mm] x\equiv\pm 1\mod{35}. [/mm] Dabei geht z.B. [mm] x\equiv{6} [/mm] verloren.
Die umgekehrte Richtung dagegen stimmt natürlich. Aus [mm] x\equiv\pm{1} [/mm] folgt offensichtlich [mm] x^4\equiv 1\mod{35}.
[/mm]
|
|
|
|
