Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat

Kleiner Satz von Fermat

Aussage

Für eine Primzahl $p$ und eine beliebige ganze Zahl $a$ gilt

a^{p}\equiv a\mod p.

Anders ausgedrückt: $a^{p}-a$ ist durch $p$ teilbar.

Vorbemerkungen

Die folgenden Vereinfachungen oder Spezialfälle werden in den Beweisen nicht eigens erklärt:

Ist $a$ durch $p$ teilbar, so gilt

a\equiv 0\equiv a^{p}\mod p.

Für nicht durch $p$ teilbare $a$ kann alternativ die äquivalente Aussage

1\equiv a^{p-1}\mod p

gezeigt werden: Die obige Version erhält man durch Multiplikation beider Seiten mit

a

; umgekehrt darf man bei Kongruenzen durch teilerfremde Zahlen teilen.

Man kann sich beim Beweis auf positive Zahlen $a$ beschränken: Für negative $a$ folgt die Aussage dann aus

(-a)^{p}-(-a)=-(a^{p}-a)

für ungerade

p

bzw.

(-a)^{2}-(-a)=a^{2}-a+2\cdot a

für

p=2

.

Restklassen modulo $p$ werden durch einen Querstrich symbolisiert, die zu beweisende Aussage ist also

{\bar {a}}^{p}={\bar {a}}

bzw.

{\bar {a}}^{p-1}={\bar {1}}

für

{\bar {a}}\neq {\bar {0}}.

Beweis 1 (Induktion)

Die Aussage wird per Induktion über $a$ für alle nichtnegativen ganzen Zahlen $a$ gezeigt.

Induktionsanfang: $0^{p}-0=0$ ist durch $p$ teilbar.

Induktionsschritt: Die Behauptung sei wahr für ein gewisses $a$ . Dann ist nach dem binomischen Satz

(a+1)^{p}-(a+1)=a^{p}+{p \choose 1}a^{p-1}+\ldots +{p \choose p-1}a+1-(a+1)

In der Darstellung

{p \choose k}={\frac {p\cdot (p-1)\cdots (p-k+1)}{1\cdot 2\cdots k}}

taucht $p$ für $1\leq k\leq p-1$ nur im Zähler auf. Da $p$ prim ist, treten im Nenner keine Teiler von $p$ auf. Die Binomialkoeffizienten sind daher alle durch $p$ teilbar. Damit folgt

(a+1)^{p}-(a+1)\equiv a^{p}+1-(a+1)=a^{p}-a\mod p,

und nach Induktionsvoraussetzung ist das durch $p$ teilbar.

Beweis 2 (Kombinatorik)

Aus Perlen von $a$ verschiedenen Farben soll eine (geschlossene) Kette mit $p$ Perlen zusammengestellt werden. Für jede Perle gibt es $a$ Wahlen, insgesamt gibt es also $a^{p}$ Möglichkeiten. Betrachtet man eine Kette und alle Ketten, die aus ihr durch Rotation hervorgehen, so gibt es zwei Möglichkeiten:

Alle Perlen der Kette haben dieselbe Farbe, es ist also nicht möglich durch Rotation eine neue Kette zu bilden.
Die Kette enthält mindestens eine andersfarbige Perle. Durch Rotation erhält man genau $p$ verschiedene Ketten.

Begründung: Es sei $k$ die kleinste Zahl, für die eine Rotation um $k$ Perlen wieder dieselbe Kette liefert. Ist $k$ kein Teiler von $p$ , so sei $nk$ das kleinste Vielfache von $k$ , das größer als $p$ ist. Es ist kleiner als $p+k$ , also ist $nk-p$ positiv und kleiner als $k$ , aber die Rotation um diese Zahl von Perlen überführt wieder die Kette in sich selbst, im Widerspruch zur Annahme, dass $k$ bereits die kleinste solche Zahl sei. Also muss $k$ ein Teiler von $p$ sein. Da $p$ eine Primzahl ist, ist $k=1$ oder $k=p$ , und diese beiden Werte entsprechen genau den beiden oben angegebenen Fällen.

Es gibt $a$ einfarbige Ketten, also ist $a^{p}-a$ die Anzahl der gemischtfarbigen Ketten. Nach der obigen Überlegungen kann man die gemischtfarbigen Ketten aber in Gruppen zu je $p$ zusammenfassen, ihre Anzahl ist also durch $p$ teilbar.

Beweis 3 (Bijektivität der Multiplikation mit a)

Es sei $a$ nicht durch $p$ teilbar. Die Abbildung

f\colon (\mathbb {Z} /p)^{\times }\to (\mathbb {Z} /p)^{\times },\quad x\mapsto a\cdot x

ist injektiv, da man bei Kongruenzen durch zum Modul $p$ teilerfremde Zahlen teilen darf: Die Aussage

ax\equiv ay\mod p

bedeutet

p\mid ax-ay=a(x-y),

und da $a$ nach Voraussetzung nicht durch $p$ teilbar ist, muss $x-y$ durch $p$ teilbar sein, d.h.

x\equiv y\mod p.

Da Definitions- und Zielbereich der Funktion $f$ dieselbe Zahl von Elementen haben, ist jede injektive Funktion automatisch bijektiv. Die Zahlen

f({\bar {1}}),f({\bar {2}}),\ldots ,f({\overline {p-1}})

sind also genau die Zahlen

{\bar {1}},{\bar {2}},\ldots ,{\overline {p-1}},

allerdings möglicherweise in anderer Reihenfolge. Also sind die Produkte gleich:

f({\bar {1}})\cdot f({\bar {2}})\cdots f({\overline {p-1}})={\bar {1}}\cdot {\bar {2}}\cdots {\overline {p-1}}.

Nun ist

f({\bar {1}})\cdot f({\bar {2}})\cdots f({\overline {p-1}})=({\bar {a}}\cdot {\bar {1}})\cdots ({\bar {a}}\cdot {\overline {p-1}})={\bar {a}}^{p-1}\cdot ({\bar {1}}\cdot {\bar {2}}\cdots {\overline {p-1}}),

also

{\bar {a}}^{p-1}\cdot ({\bar {1}}\cdot {\bar {2}}\cdots {\overline {p-1}})={\bar {1}}\cdot ({\bar {1}}\cdot {\bar {2}}\cdots {\overline {p-1}}).

Da die Zahlen $1,2,\ldots ,p-1$ alle teilerfremd zu $p$ sind, darf man durch das geklammerte Produkt teilen, und es ergibt sich die Aussage

{\bar {a}}^{p-1}={\bar {1}}

oder anders geschrieben

a^{p-1}\equiv 1\mod p.

Beweis 4 (Gruppentheorie)

Ist $a$ nicht durch $p$ teilbar, so definiert $a$ ein Element ${\bar {a}}$ in der Gruppe $(\mathbb {Z} /p)^{\times }$ ; diese Gruppe hat die Ordnung $p-1$ , und nach dem Satz von Lagrange gilt