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


Kleiner Satz von Fermat

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