Eulertest und Carmichael-Zahl < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:00 Mi 18.07.2012 | | Autor: | Frisco |
Hallo 
Wir hatten in der Vorlesung den Eulerschen Primzahltest, welcher auf dem Euler-Kriterium beruht, dieser Satz ist soweit klar!
Es ist auch durch ein Zahlen Beispiel N=561 klar, dass dieses Kriterium auch Carmichael-Zahlen "enttarnen" kann.
Nun hat unser Prof eine "mündliche" Bemerkung in der Vorlesung gemacht, die ich nicht ganz verstehe, er meinte:
Der Eulertest enttarnt genau die Carmichael-Zahlen als zusammengesetzt für die gilt:
[mm] \lambda(N) [/mm] ist kein Teiler von [mm] \frac{N-1}{2}
[/mm]
wobei [mm] \lambda(N) [/mm] die Carmichael-Funktion ist.
Warum gilt das??
Kann mir jemand Tips geben bzw. eine Beweisskizze angeben
Ein Beispiel dafür ist die kleinste Carmichael-Zahl N=561
denn [mm] \lambda{561}=kgV(2, [/mm] 10, 16)=80 und die ist offensichtlich kein Teiler von [mm] 280=\frac{561-1}{2}
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:53 Do 19.07.2012 | | Autor: | felixf |
Moin!
> Wir hatten in der Vorlesung den Eulerschen Primzahltest,
> welcher auf dem Euler-Kriterium beruht, dieser Satz ist
> soweit klar!
> Es ist auch durch ein Zahlen Beispiel N=561 klar, dass
> dieses Kriterium auch Carmichael-Zahlen "enttarnen" kann.
> Nun hat unser Prof eine "mündliche" Bemerkung in der
> Vorlesung gemacht, die ich nicht ganz verstehe, er meinte:
> Der Eulertest enttarnt genau die Carmichael-Zahlen als
> zusammengesetzt für die gilt:
> [mm]\lambda(N)[/mm] ist kein Teiler von [mm]\frac{N-1}{2}[/mm]
> wobei [mm]\lambda(N)[/mm] die Carmichael-Funktion ist.
> Warum gilt das??
Wenn [mm] $\lambda(N) \mid \frac{N - 1}{2}$ [/mm] ist, dann gilt [mm] $a^{\frac{N - 1}{2}} \equiv [/mm] 1 [mm] \pmod{N}$ [/mm] fuer jedes $a$, welches teilerfremd zu $N$ ist. Damit wird $N$ vom Eulertest nicht enttarnt.
Ist andersherum [mm] $\lambda(N)$ [/mm] kein Teiler von [mm] $\frac{N - 1}{2}$, [/mm] so sei $p$ eine Primzahl, die [mm] $\lambda(N)$ [/mm] teilt, aber nicht [mm] $\frac{N - 1}{2}$. [/mm] (Dies geht, da bei Carmichael-Zahlen [mm] $\lambda(N)$ [/mm] ein Teiler von $N - 1$ ist.) Da [mm] $\lambda(N)$ [/mm] der Exponent der Gruppenordnung von [mm] $(\IZ/N\IZ)^\ast$ [/mm] ist, gibt es nach den Sylow-Saetzen (bzw. dem ![[]](/images/popup.gif) Satz von Cauchy) ein Element $g [mm] \in (\IZ/N\IZ)^\ast$ [/mm] welches die Ordnung $p$ hat. Da [mm] $\frac{N - 1}{2}$ [/mm] teilerfremd zu $p$ ist liegt [mm] $g^{\frac{N - 1}{2}}$ [/mm] in der von $g$ erzeugten Untergruppe, ist jedoch nicht die Identitaet. Ist $p [mm] \neq [/mm] 2$, so folgt daraus, dass $N$ vom Eulertest enttarnt wird. Falls nur $p = 2$ moeglich ist, so muss [mm] $\lambda(N) [/mm] = N - 1$ sein (und $N [mm] \equiv [/mm] 3 [mm] \pmod{4}$). [/mm] Da jedoch [mm] $\lambda(N)$ [/mm] ein Teiler von [mm] $\varphi(N)$ [/mm] ist folgt, dass $N$ prim ist, ein Widerspruch.
LG Felix
|
|
|
|
