Pseudoprimzahlen: Der kleine Fermatsche Satz

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

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

Für jede Primzahl gilt, das für jede natürliche Zahl der Ausdruck durch teilbar ist. Ebenso gilt für jede Carmichael-Zahl , das für jede natürliche Zahl der Ausdruck durch 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 gilt: für jede natürliche Zahl , die teilerfremd zu ist.

Das bedeutet, das der kleine fermatsche Satz für nicht gilt: . Ähnliches gilt für jede Carmichael-Zahl : . Aber es gilt genauso für alle Primteiler der entsprechenden Carmichael-Zahl : .

2 ≤ a ≤ n-2 statt 2 ≤ a ≤ n-1[Bearbeiten]