Der kleine Satz von Fermat

Fermat und Euler · Abschnitt 25 von 64

Satz

Kleiner Satz von Fermat

Ist $p$ prim und $p\nmid a$ , dann gilt $a^{p-1}\equiv1\pmod p$ . Für jedes ganze $a$ gilt außerdem $a^p\equiv a\pmod p$ .

Beweis

Beweis durch Permutation

Die Reste $a,2a,\ldots,(p-1)a$ sind modulo $p$ paarweise verschieden und von null verschieden. Sie sind daher nur eine Umordnung von $1,2,\ldots,p-1$ . Aus $a^{p-1}(p-1)!\equiv(p-1)!$ darf der invertierbare Faktor $(p-1)!$ gekürzt werden.

Gelöstes Beispiel

Exponent modulo zwölf

Modulo 13 gilt für $13\nmid a$ die Kongruenz $a^{12}\equiv1$ . Daher darf ein positiver Exponent in Blöcke der Länge 12 zerlegt werden.

Achtung

Primzahl und Basis prüfen

Die Form $a^{p-1}\equiv1$ verlangt sowohl ein Primzahlmodul als auch $p\nmid a$ . Die Form $a^p\equiv a$ gilt dagegen für alle ganzen $a$ .