Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat

Aus Wikibooks

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

Algebraische Zahlentheorie: Pythagoraszahl nicht-reeller Körper

Analytische Zahlentheorie: Irrationalität von

ζ(3)

· Primzahlsatz

[Bearbeiten] Kleiner Satz von Fermat

[Bearbeiten] Aussage

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

$a\equiv a^p\mod p.$

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

[Bearbeiten] 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.$

[Bearbeiten] 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 $\equiv0$ .

[Bearbeiten] 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.
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 $n k$ das kleinste Vielfache von $k$ , das größer als $p$ ist. Es ist kleiner als $p + k$ , also ist $n k - 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.

[Bearbeiten] 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.$

[Bearbeiten] 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