Pseudoprimzahlen: Der kleine Fermatsche Satz

Pseudoprimzahlen

Der kleine Fermatsche Satz besagt, dass $\ a^{p}-a\$ für jede Primzahl$\ p\$und jede natürliche Zahl $a\geq 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{\pmod {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{\pmod {p}}$ ableiten. Die Aussage: "$a^{p-1}-1\$ ist durch $p\$ teilbar" und die Formel $a^{p-1}\equiv 1{\pmod {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{\pmod {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}\not \equiv 1\ {\pmod {p}}$. Ähnliches gilt für jede Carmichael-Zahl $c\$: $c^{c-1}\not \equiv 1\ {\pmod {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}\not \equiv 1\ {\pmod {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{\pmod {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{\pmod {p}}$ oder
• $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ gelten.