Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat

Beweisarchiv: Zahlentheorie

Elementare Zahlentheorie: Kleiner Satz von Fermat · Satz von Euklid · Satz von Wilson · Vollständige Multiplikativität der p-adischen Exponentenbewertung

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 amodp.$

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}modp.$

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

$1\equiv a^{p-1}modp$

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

${\overline{a}}^p=\overline{a}$ bzw. ${\overline{a}}^{p-1}=\overline{1}$ für $\overline{a}\ne \overline{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+(\genfrac{}{}{0ex}{}{p}{1})a^{p-1}+\dots +(\genfrac{}{}{0ex}{}{p}{p-1})a+1-(a+1)$

In der Darstellung

$(\genfrac{}{}{0ex}{}{p}{k})=\frac{p\cdot (p-1)\cdots (p-k+1)}{1\cdot 2\cdots k}$

taucht $p$ für $1\le k\le 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-amodp,$

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:(\mathbb{Z}/p{)}^{\times }\to (\mathbb{Z}/p{)}^{\times },x\mapsto a\cdot x$

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

$ax\equiv aymodp$

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 ymodp.$

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

$f(\overline{1}),f(\overline{2}),\dots ,f(\overline{p-1})$

sind also genau die Zahlen

$\overline{1},\overline{2},\dots ,\overline{p-1},$

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

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

Nun ist

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

also

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

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

${\overline{a}}^{p-1}=\overline{1}$

oder anders geschrieben

$a^{p-1}\equiv 1modp.$

Beweis 4 (Gruppentheorie)

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

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

anders ausgedrückt

$a^{p-1}\equiv 1modp.$

Durch Multiplikation mit $a$ ergibt sich die Behauptung.

Anmerkung: Genau dasselbe Argument zeigt auch die allgemeinere Aussage

$a^{\phi (n)}\equiv 1modn$

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

Wikipedia-Verweise

• Kleiner fermatscher Satz
• Kongruenzen