Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat

Aus Wikibooks

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 · Primzahlsatz


Kleiner Satz von Fermat[Bearbeiten]

Aussage[Bearbeiten]

Für eine Primzahl und eine beliebige ganze Zahl gilt

Anders ausgedrückt: ist durch teilbar.

Vorbemerkungen[Bearbeiten]

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

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

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

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

Ist 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.

Wikipedia-Verweise[Bearbeiten]