Primzahltest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:42 Sa 01.11.2008 | | Autor: | Irmchen |
Hallo alle zusammen!
Ich beschäftige mich gerade mit dem Thema der Primzahltest von Solovay und Strassen und dem Satz, auf dem der Test beruht. Den Satz habe ich verstanden, aber leider habe ein paar Schwierigkeiten bei Beweis.
Satz :
Sei n eine ungerade natürliche Zahl größer 1. Dann sind äquivalent:
1. n ist eine Primzahl
2. Für alle [mm] a \in \mathbb Z [/mm] mit [mm] ggT(a,n) = 1 [/mm] gilt:
[mm] a^{ \bruch{n-1}{2}} \equiv ( \bruch{a}{n} ) \mod n [/mm]
Beweis :
[mm] 2 \Rightarrow 1 [/mm]:
Es gilt [mm] ( \bruch{a}{n} ) \mp 1 \ \forall a [/mm].
Es folgt [mm] a^{n-1} \equiv 1 \mod n [/mm] Warum folgt das ? .
Deswegen ist n quadratfrei, d.h. [mm] n = p_1 \cdot ... \cdot p_r [/mm] mit verschiedenen ungeraden Primzahlen.
Angenommen r> 1.
Wähle [mm] g \in \mathbb Z [/mm] ein Nichtquadrat mod [mm] p_1 [/mm] und [mm] a \in \mathbb Z [/mm] mit
[mm] a \equiv g \mod p_1 [/mm]
[mm] a \equiv 1 \mod p_2 \cdot ... \cdot p_r [/mm]
Was will man mit diesen 2 Kongruenzen zeigen?
Es gilt:
[mm] ( \bruch{a}{n} ) = ( \bruch{a}{p_1} ) ( \bruch{a}{p_2 \cdot ... \cdot p_r} ) = -1 [/mm]
Woher weiß man, dass das -1 ist? q ist ein Nichtquadrat und somit auch (
wegen den Regeln für Jacobi - Symbol auch [mm] ( \bruch{a}{p_1} )[/mm]. Aber woher weiß ich, dass [mm] ( \bruch{a}{p_2 \cdot ... \cdot p_r} ) = -1 [/mm] ein quadratischer Rest ist?
Außerdem gilt:
[mm] ( \bruch{a}{n} ) \equiv a^{ \bruch{n-1}{2} } \mod p_2 [/mm]
[mm] -1 \equiv 1 \mod p_2 [/mm] (+)
da [mm] a \equiv 1 \mod p_2 [/mm]
Warum gilt (+) ?
Also ist hier ein Widerspruch entstanden und somit gezeigt dass n eine Primzahl ist.
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:24 Di 04.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
