Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat
- 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 · Primzahlsatz
Kleiner Satz von Fermat
BearbeitenAussage
BearbeitenFür eine Primzahl und eine beliebige ganze Zahl gilt
Anders ausgedrückt: ist durch teilbar.
Vorbemerkungen
BearbeitenDie folgenden Vereinfachungen oder Spezialfälle werden in den Beweisen nicht eigens erklärt:
- Ist durch teilbar, so gilt
- Für nicht durch teilbare kann alternativ die äquivalente Aussage
- gezeigt werden: Die obige Version erhält man durch Multiplikation beider Seiten mit ; umgekehrt darf man bei Kongruenzen durch teilerfremde Zahlen teilen.
- Man kann sich beim Beweis auf positive Zahlen beschränken: Für negative folgt die Aussage dann aus
- für ungerade
- bzw.
- für .
- Restklassen modulo werden durch einen Querstrich symbolisiert, die zu beweisende Aussage ist also
- bzw. für
Beweis 1 (Induktion)
BearbeitenDie Aussage wird per Induktion über für alle nichtnegativen ganzen Zahlen gezeigt.
Induktionsanfang: ist durch teilbar.
Induktionsschritt: Die Behauptung sei wahr für ein gewisses . Dann ist nach dem binomischen Satz
In der Darstellung
taucht für nur im Zähler auf. Da prim ist, treten im Nenner keine Teiler von auf. Die Binomialkoeffizienten sind daher alle durch teilbar. Damit folgt
und nach Induktionsvoraussetzung ist das durch teilbar.
Beweis 2 (Kombinatorik)
BearbeitenAus Perlen von verschiedenen Farben soll eine (geschlossene) Kette mit Perlen zusammengestellt werden. Für jede Perle gibt es Wahlen, insgesamt gibt es also 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 verschiedene Ketten.
Begründung: Es sei die kleinste Zahl, für die eine Rotation um Perlen wieder dieselbe Kette liefert. Ist kein Teiler von , so sei das kleinste Vielfache von , das größer als ist. Es ist kleiner als , also ist positiv und kleiner als , aber die Rotation um diese Zahl von Perlen überführt wieder die Kette in sich selbst, im Widerspruch zur Annahme, dass bereits die kleinste solche Zahl sei. Also muss ein Teiler von sein. Da eine Primzahl ist, ist oder , und diese beiden Werte entsprechen genau den beiden oben angegebenen Fällen.
Es gibt einfarbige Ketten, also ist die Anzahl der gemischtfarbigen Ketten. Nach der obigen Überlegungen kann man die gemischtfarbigen Ketten aber in Gruppen zu je zusammenfassen, ihre Anzahl ist also durch teilbar.
Beweis 3 (Bijektivität der Multiplikation mit a)
BearbeitenEs sei nicht durch teilbar. Die Abbildung
ist injektiv, da man bei Kongruenzen durch zum Modul teilerfremde Zahlen teilen darf: Die Aussage
bedeutet
und da nach Voraussetzung nicht durch teilbar ist, muss durch teilbar sein, d.h.
Da Definitions- und Zielbereich der Funktion dieselbe Zahl von Elementen haben, ist jede injektive Funktion automatisch bijektiv. Die Zahlen
sind also genau die Zahlen
allerdings möglicherweise in anderer Reihenfolge. Also sind die Produkte gleich:
Nun ist
also
Da die Zahlen alle teilerfremd zu sind, darf man durch das geklammerte Produkt teilen, und es ergibt sich die Aussage
oder anders geschrieben
Beweis 4 (Gruppentheorie)
BearbeitenIst nicht durch teilbar, so definiert ein Element in der Gruppe ; diese Gruppe hat die Ordnung , und nach dem Satz von Lagrange gilt
anders ausgedrückt
Durch Multiplikation mit ergibt sich die Behauptung.
Anmerkung: Genau dasselbe Argument zeigt auch die allgemeinere Aussage
für , die als Satz von Euler-Fermat bezeichnet wird.