Pseudoprimzahlen: Der kleine Fermatsche Satz

Der kleine Fermatsche Satz besagt, dass $a^p-a$ für jede Primzahl$p$und jede natürliche Zahl $a\ge 2$durch$p$teilbar ist.

Beispiel anhand der Primzahl 5:

• $2^5-2=5\cdot 6$
• $3^5-3=5\cdot 48$
• $4^5-4=5\cdot 204$

Ableitungen

Statt der Aussage: "$a^p-a$ ist (ohne Rest) durch $p$ teilbar", kann man auch $a^p\equiv a(\mathrm{mod}p)$ schreiben. Wenn man $a$ aus $a^p-a$ ausklammert, kommt man auf einen Ausdruck $a\cdot (a^{p-1}-1)$. Da $a\cdot (a^{p-1}-1)$ durch $p$ teilbar ist, aber $a$ nicht zwangsläufig durch $p$ teilbar ist, muss es der Ausdruck $(a^{p-1}-1)$ sein, der immer durch $p$ teilbar ist. Aus der Aussage: "$a^{p-1}-1$ ist durch $p$ teilbar", kann man $a^{p-1}\equiv 1(\mathrm{mod}p)$ ableiten. Die Aussage: "$a^{p-1}-1$ ist durch $p$ teilbar" und die Formel $a^{p-1}\equiv 1(\mathrm{mod}p)$ gelten allerdings nur, wenn die Basis $a$ teilerfremd zur Primzahl $p$ ist.

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

Für jede Primzahl $p$ gilt, dass für jede natürliche Zahl $a$ der Ausdruck $a^p-a$durch $p$ teilbar ist. Ebenso gilt für jede Carmichael-Zahl $c$, dass 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 das Problem anzugehen, aber dafür hilft auch eine Modifikation des kleinen Fermatschen Satzes:

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

Das bedeutet, dass der kleine fermatsche Satz für $a=p$ nicht gilt: $p^{p-1}\equiv ̸1(\mathrm{mod}p)$. Ähnliches gilt für jede Carmichael-Zahl $c$: $c^{c-1}\equiv ̸1(\mathrm{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$: $p_m^{c-1}\equiv ̸1(\mathrm{mod}c)$.

Folgerung durch Euler

Auf den kleinen Fermatschen Satz lässt sich die dritte binomische Formel $a^2-b^2=(a+b)\cdot (a-b)$ anwenden:

$a^{p-1}-1=(a^{\frac{p-1}{2}}+1)\cdot (a^{\frac{p-1}{2}}-1)\equiv 0(\mathrm{mod}p)$.

Das bedeutet, dass genau einer der beiden Faktoren durch $p$teilbar sein muss, dass also $a^{\frac{p-1}{2}}+1$ oder $a^{\frac{p-1}{2}}-1$ durch $p$teilbar ist. Das führt zu dem Satz, der Leonhard Euler zugesprochen wird:

Wenn $p$ eine ungerade Primzahl ist, muss entweder

• $a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$ oder
• $a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$ gelten.