Primzahlkrit. Frage zu Beweis < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:42 Mo 28.02.2011 | | Autor: | Vicky89 |
| Aufgabe | Genau dann ist p eine primzahl, wenn (p-1)! [mm] \equiv [/mm] -1 mod p
Beweis: Es sei p|(p-1)!+1. Ist [mm] 1\le [/mm] d < p und d|p, dann folgt d|(p-1)! und damit auch d|1 .... |
Hallo,
ich habe ein Frage zu obigen Beweis.
Einmal eine Verständnisfrage. Bedeutet p|(p-1)!+1 p teilt ((p-1!)!+1)? Also p teilt die Summe von (p-1)! und 1. Ja, oder?
Dann verstehe ich aber nicht, wieso aus d|p folgt, dass d|(p-1)! und damit auch d|1.
Wieso teilt d die einzelnen Summanden? Das ist mir irgendwie nicht so ganz klar...
Liebe Grüße
|
|
| |
|
Hallo,
> Genau dann ist p eine primzahl, wenn (p-1)! [mm]\equiv[/mm] -1 mod
> p
> Beweis: Es sei p|(p-1)!+1. Ist [mm]1\le[/mm] d < p und d|p, dann
> folgt d|(p-1)! und damit auch d|1 ....
>
> Hallo,
> ich habe ein Frage zu obigen Beweis.
> Einmal eine Verständnisfrage. Bedeutet p|(p-1)!+1, dass p teilt
> ((p-1!)!+1)? Also p teilt die Summe von (p-1)! und 1. Ja,
> oder?
Vorsicht wenn du zwei Aussagen wir hier ohne Punkt und Komma aneinander reihst. Da können leicht noch mehr Missverständnisse entstehen.
Aber ja, du hast es schon richtig verstanden.
>
> Dann verstehe ich aber nicht, wieso aus d|p folgt, dass
> d|(p-1)!
d ist einer der Faktoren von (p-1)!, da [mm] $1\leq [/mm] d<p$. Also d|(p-1)! [mm] (\*)
[/mm]
> und damit auch d|1.
Es wurde nun angenommen, dass p|(p-1)!+1 [mm] (\*\*), [/mm] was aus [mm] $(p-1)!\equiv [/mm] -1 [mm] \mod [/mm] p$ folgt.
Dann wird gesagt, dass d ein Teiler von p sei mit [mm] $1\leq [/mm] d<p$. Wegen [mm] (\*\*) [/mm] muss d|(p-1)!+1 sein.
Wegen [mm] (\*) [/mm] ist d ein Teiler von (p-1)!. Wäre nun d kein Teiler von 1, so könnte d nicht mehr Teiler von (p-1)!+1 sein, Widerspruch! Also ist d|1
> Wieso teilt d die einzelnen Summanden? Das ist mir
> irgendwie nicht so ganz klar...
Es gilt die Teilbarkeitseigenschaft [mm] \left(a|b \wedge a|(b+c)\right) \Rightarrow [/mm] a|c.
Das kann man leicht überprüfen.
>
> Liebe Grüße
Gruß
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:27 Sa 05.03.2011 | | Autor: | Vicky89 |
Hallo,
vielen Dank. Ja, eignetlich total logisch, dass d , (p-1)! teilen muss, wenn es kleiner ist. Habe das nicht miteinander in Zusammenhang gebracht.
Aber mit dem Rest des Beweises komme ich auch nicht so wirklich klar, vielleicht kann mir da ja auch jemand helfen.
p ist also eine Primzahl. klar
Ist p nun >2, so ex. primitive Restklasse [a] modulo p. Dann gilt:
[mm] (p-1)!\equiv a*a^{2}*...*a^{p-1} \equiv a^{p}^{\bruch{p-1}{2}} \equiv a^{\bruch{p-1}{2}} [/mm] mod p
ich verstehe die äquivalenzaussagen nicht so wirklich... ich kann nicht so ganz erkennen, in wie fern das äquivalent ist...
Für [mm] x=a^{\bruch{p-1}{2}} [/mm] ist [mm] x^{2} \equiv [/mm] 1 mod p, also p|(x-a)(x+1). Da[a] primitiv ist, gilt [mm] !\equiv [/mm] 1 mod p, es muss also [mm] \equiv [/mm] -1 mod p gelten.
ich komme mit mod nicht so ganz klar. Ich weiß nicht, wie man darauf kommt..
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:31 So 06.03.2011 | | Autor: | abakus |
> Hallo,
> vielen Dank. Ja, eignetlich total logisch, dass d , (p-1)!
> teilen muss, wenn es kleiner ist. Habe das nicht
> miteinander in Zusammenhang gebracht.
> Aber mit dem Rest des Beweises komme ich auch nicht so
> wirklich klar, vielleicht kann mir da ja auch jemand
> helfen.
>
> p ist also eine Primzahl. klar
>
> Ist p nun >2, so ex. primitive Restklasse [a] modulo p.
> Dann gilt:
> [mm](p-1)!\equiv a*a^{2}*...*a^{p-1} \equiv a^{p}^{\bruch{p-1}{2}} \equiv a^{\bruch{p-1}{2}}[/mm]
> mod p
>
> ich verstehe die äquivalenzaussagen nicht so wirklich...
> ich kann nicht so ganz erkennen, in wie fern das
> äquivalent ist...
Hallo,
die Potenzen a, [mm] a^2, a^3, [/mm] ... [mm] a^{p-1} [/mm] lassen jeweils verschiedene Reste bei Teilung durch p. Somit tritt in diesen Potenzen (in irgendeiner ungeordneten Reihenfolge) jeder Rest von 1 bis p-1 genau einmal auf, wobei Rest 1 der letzte Rest ist. Danach beginnt diese Restefolge von vorn; wegen [mm] a^{p-1}\equiv [/mm] 1 mod p gilt dann auch [mm] a*a^{p-1}\equiv [/mm] a mod p, [mm] a^2*a^{p-1}\equiv a^2 [/mm] mod p usw.
Also gilt [mm] a^k\equiv a^{k+(p-1)} [/mm] für jeden beliebigen Exponenten k.
Gruß Abakus
>
> Für [mm]x=a^{\bruch{p-1}{2}}[/mm] ist [mm]x^{2} \equiv[/mm] 1 mod p, also
> p|(x-a)(x+1). Da[a] primitiv ist, gilt [mm]!\equiv[/mm] 1 mod p, es
> muss also [mm]\equiv[/mm] -1 mod p gelten.
>
> ich komme mit mod nicht so ganz klar. Ich weiß nicht, wie
> man darauf kommt..
>
> lg
>
|
|
|
|
