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

Für jede Primzahl ${\displaystyle p\ }$ gilt, das für jede natürliche Zahl ${\displaystyle a\ }$ der Ausdruck ${\displaystyle a^{p}-a\ }$ durch ${\displaystyle p\ }$ teilbar ist. Ebenso gilt für jede Carmichael-Zahl ${\displaystyle c\ }$, das für jede natürliche Zahl ${\displaystyle a\ }$ der Ausdruck ${\displaystyle a^{c}-a\ }$ durch ${\displaystyle 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 ${\displaystyle p\ }$ gilt: ${\displaystyle a^{p-1}\equiv 1(\mod p)}$ für jede natürliche Zahl ${\displaystyle a\ }$, die teilerfremd zu ${\displaystyle p\ }$ ist.

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

2 ≤ a ≤ n-2 statt 2 ≤ a ≤ n-1