Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat

Beweisarchiv: Zahlentheorie

Elementare Zahlentheorie: Kleiner Satz von Fermat · Satz von Euklid · Satz von Wilson

Algebraische Zahlentheorie: Pythagoraszahl nicht-reeller Körper · Korrespondenzsatz der algebraischen Zahlentheorie · Zerlegungsgesetz

Analytische Zahlentheorie: Irrationalität von $\zeta(3)$ · Primzahlsatz

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

$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}=\bar1$ für $\bar a\ne\bar0.$

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)$

Die Binomialkoeffizienten sind alle durch $p$ teilbar: In der Darstellung

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

taucht $p$ für $1\leq k\leq p-1$ nur im Zähler auf. 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 sein. 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

$\bar1,\bar2,\ldots,\overline{p-1},$

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

$f(\bar1)\cdot f(\bar2)\cdots f(\overline{p-1})=\bar1\cdot\bar2\cdots\overline{p-1}.$

Nun ist

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

also

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

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

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

oder anders geschrieben

$a^{p-1}\equiv1\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

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

anders ausgedrückt

$a^{p-1}\equiv1\mod p.$

Durch Multiplikation mit $a$ ergibt sich die Behauptung.

Anmerkung: Genau dasselbe Argument zeigt auch die allgemeinere Aussage

$a^{\varphi(n)}\equiv1\mod n$

für $(a,n)=1$, die als Satz von Euler-Fermat bezeichnet wird.

Wikipedia-Verweise

Kleiner fermatscher Satz - Kongruenzen

---

Beweisarchiv: Zahlentheorie

Elementare Zahlentheorie: Kleiner Satz von Fermat · Satz von Euklid · Satz von Wilson

Algebraische Zahlentheorie: Pythagoraszahl nicht-reeller Körper · Korrespondenzsatz der algebraischen Zahlentheorie · Zerlegungsgesetz

Analytische Zahlentheorie: Irrationalität von $\zeta(3)$ · Primzahlsatz