Pseudoprimzahlen: Der kleine Fermatsche Satz

Aus Wikibooks

[Bearbeiten] Was unterscheidet aⁿ ≡ a (mod n) von a^n-1 ≡ 1 (mod n)

Für jede Primzahl $p\$ gilt, das für jede natürliche Zahl $a\$ der Ausdruck $a^p - a\$ durch $p\$ teilbar ist. Ebenso gilt für jede Carmichael-Zahl $c\$ , das für jede natürliche Zahl $a\$ der Ausdruck $a^c - a\$ durch $c\$ teilbar ist.

Ja aber bitte wie unterscheidet man dann eine Primzahl von einer Carmichael-Zahl?

Es gibt natürlich noch andere Wege, um an das Problem zu gehen, aber dafür hilft auch eine Modifikation des kleinen Fermatschen Satzes:

Für jede Primzahl $p\$ gilt: $a^{p-1} \equiv 1 (\mod p)$ für jede natürliche Zahl $a\$ , die teilerfremd zu $p\$ ist.

Das bedeutet, das der kleine fermatsche Satz für $a = p\$ nicht gilt: $p^{p-1} \not\equiv 1 (\mod p)$ . Ähnliches gilt für jede Carmichael-Zahl $c\$ : $c^{c-1} \not\equiv 1 (\mod c)$ . Aber es gilt genauso für alle Primteiler $p_m\$ der entsprechenden Carmichael-Zahl $c = p_1 \cdot p_2 \cdot ... \cdot p_n$ : $c^{p_n-1} \not\equiv 1 (\mod c)$ .