Zum Inhalt springen

Pseudoprimzahlen: Der kleine Fermatsche Satz

Aus Wikibooks

Der kleine Fermatsche Satz besagt, dass für jede Primzahlund jede natürliche Zahl durchteilbar ist.

Beispiel anhand der Primzahl 5:

Ableitungen

[Bearbeiten]

Statt der Aussage: " ist (ohne Rest) durch teilbar", kann man auch schreiben. Wenn man aus ausklammert, kommt man auf einen Ausdruck . Da durch teilbar ist, aber nicht zwangsläufig durch teilbar ist, muss es der Ausdruck sein, der immer durch teilbar ist. Aus der Aussage: " ist durch teilbar", kann man ableiten. Die Aussage: " ist durch teilbar" und die Formel gelten allerdings nur, wenn die Basis teilerfremd zur Primzahl ist.

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

[Bearbeiten]

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

Folgerung durch Euler

[Bearbeiten]

Auf den kleinen Fermatschen Satz lässt sich die dritte binomische Formel anwenden:

.

Das bedeutet, dass genau einer der beiden Faktoren durch teilbar sein muss, dass also oder durch teilbar ist. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird:

Wenn eine ungerade Primzahl ist, muss entweder

  • oder
  • gelten.