Fermat -Test < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:23 Fr 24.10.2008 | | Autor: | Irmchen |
Guten Tag!
Ich habe hier den Primzahltest Fermat - Test und rechne gerade Beispiele durch.
Der FERMAT - TEST beruht auf den folgenden Satz:
Sei [mm] n \in \mathbb N [/mm] ungerade.
Angenommen es gibt ein [mm] a \in \mathbb Z [/mm] mit ggT (a,n) = 1
und
[mm] a^{n-1} \not \equiv 1 \mod n [/mm]
Dann ist n keine Primzahl.
Nun stellt sich die Frage, ob die Umkehrung dieses Satzes gilt, d.h.
ob aus der Bedingung
[mm] a^{n-1} \equiv 1 \mod n [/mm] für alle [mm] a \in \mathbb Z [/mm] mit ggT (a,n) = 1
folgt, dass n eine Primzahl ist.
Das ist nicht der Fall und als Beispiel dafür sind die Carmichael - Zahlen.
DEFINITION :
Sei [mm] n \in \mathbb N [/mm] , n ungerade heißt Carmichael -Zahl, falls
[mm] a^{n-1} \equiv 1 \mod n [/mm]
für alle [mm] a \in \mathbb Z [/mm] mit ggT (a,n ) = 1 und falls n keine Primzahl ist.
So, ich habe diesen Sachverhalt verstanden. Aber bei einem Beispiel, wo man zeigt, dass n = 561 eine Carmichael -Zahl ist, also die Umkehrung des Satzes erfüllt, habe ich Probleme die Rechnung zu verstehen...
Ich hoffe, dass mir jemand erklären kann, was man genau macht...
Beispiel :
[mm] n = 561 = 3 \cdot 11 \cdot 17 [/mm]
Für jedes [mm] a \in \{ 1, ... , n-1 \} [/mm] mit ggT (a,n ) =1 gilt:
[mm] a^{n-1} \equiv 1 \mod n [/mm]
[mm] a \in ( \mathbb Z / 561 \mathbb Z )^{ \* } = ( \mathbb Z / 3 \mathbb Z )^{ \* } \times ( \mathbb Z / 11 \mathbb Z )^{ \* } \times ( \mathbb Z / 17 \mathbb Z )^{ \* } [/mm]
[mm] \cong \mathbb Z / 2 \mathbb Z \times \mathbb Z / 10 \mathbb Z \times \mathbb Z / 16 \mathbb Z [/mm]
So, ab hier versteh ich nicht mehr....
[mm] \Rightarrow a^{5 \cdot 16 } \cong 1 \mod 561 [/mm]
[mm] \Rightarrow a^{560 } \cong 1 \mod 561 [/mm]
Was hat man nun hier gezeigt? Warum [mm] a^{5 \cdot 16 } [/mm] ?
Das ist ja 80 und 80 = kgV ( 2, 10, 16 ) ... Deswegen 80 ?
Woher weißt man, dass [mm] a^{5 \cdot 16 } \cong 1 \mod 561 [/mm]
[/mm] gilt ohne dass man a genau kennt? Und warum folgt dann
[mm] a^{560 } \cong 1 \mod 561 [/mm] ?
Ich hoffe, dass mir jemand diese Fragen erläutern kann.
Vielen Dank im voraus!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:29 So 26.10.2008 | | Autor: | statler |
Hi!
> [mm]a \in ( \mathbb Z / 561 \mathbb Z )^{ \* } = ( \mathbb Z / 3 \mathbb Z )^{ \* } \times ( \mathbb Z / 11 \mathbb Z )^{ \* } \times ( \mathbb Z / 17 \mathbb Z )^{ \* } [/mm]
>
> [mm]\cong \mathbb Z / 2 \mathbb Z \times \mathbb Z / 10 \mathbb Z \times \mathbb Z / 16 \mathbb Z [/mm]
Für alle x aus der unteren Gruppe - also auch für das Bild von a - gilt 80x = 0. Wegen der Isomorphie bedeutet das [mm] a^{80} [/mm] = 1.
Gruß
Dieter
|
|
|
|
