Kleiner fermatscher Satz

Der kleine fermatsche Satz, kurz „der kleine Fermat“, ist ein Lehrsatz der Zahlentheorie. Er macht eine Aussage über die Eigenschaften von Primzahlen und wurde im 17. Jahrhundert von Pierre de Fermat aufgestellt. Der Satz beschreibt die allgemein gültige Kongruenz:

Satz 1645 (Kleiner fermatscher Satz)

\(\displaystyle a^p \equiv a \mod{p},\)
wobei \(\displaystyle a\) eine ganze Zahl und \(\displaystyle p\) eine Primzahl ist.
Falls \(\displaystyle a\) kein Vielfaches von \(\displaystyle p\) ist, kann man das Resultat in die häufig benutzte Form
\(\displaystyle a^{p-1} \equiv 1 \mod{p}\)
bringen.
 
 

Beweis

Wir müssen zeigen, dass \(\displaystyle p|(a^p-p)\) ist.
Mittels vollständiger Induktion über \(\displaystyle a\) ergibt sich:
Induktionsanfang: \(\displaystyle 0^p-0=0\) ist durch \(\displaystyle p\) teilbar.
Induktionsschritt: Sei nun \(\displaystyle p|(a^p-p)\). Nach dem binomischen Satz gilt:
\(\displaystyle (a+1)^p-(a+1)=a^p+{\chooseNT p 1}a^{p-1}+\ldots+{\chooseNT p {p-1}}a+1-(a+1)\)
Die Binomialkoeffizienten sind alle durch \(\displaystyle p\) teilbar, denn in der Darstellung
\(\displaystyle {\chooseNT p k}=\dfrac{p\cdot(p-1)\cdots(p-k+1)}{1\cdot2\cdots k}\)
taucht \(\displaystyle p\) für \(\displaystyle 1\leq k\leq p\) nur im Zähler auf. Damit folgt : \(\displaystyle (a+1)^p-(a+1)\equiv a^p+1-(a+1)\) \(\displaystyle \equiv a^p-a\mod p\), und nach Induktionsvoraussetzung ist das \(\displaystyle \equiv0\).
Für \(\displaystyle a<0\) und \(\displaystyle p=2\) ist die Behauptung trivial, da \(\displaystyle a^2=(-a)^2\). Für \(\displaystyle p>2\) gilt - da alle \(\displaystyle p\) dann ungerade sind:
\(\displaystyle a^p-p=- |a|^p-p=-(|a|^p-p)+2p\)
Nun ist wegen dem oben Bewiesen aber \(\displaystyle p\) Teiler der rechten Seite. \(\displaystyle \qed\)

Bemerkung

In obigen Beweis wurde gleichzeitig die Behauptung
\(\displaystyle p|\, \chooseNT p k\)
für \(\displaystyle p\) prim und \(\displaystyle 1\leq k\leq p-1\) gezeigt. Mit dem binomischen Satz gilt dann
\(\displaystyle (a+b)^p\equiv a^p +b^p \mod p\)

Folgerung durch Euler

Ist \(\displaystyle p\) eine ungerade Primzahl, so gilt für eine beliebige ganze Zahl \(\displaystyle a\).
\(\displaystyle (a^{(p-1)/2}-1) \cdot (a^{(p-1)/2}+1) = a^{p-1} - 1\)
Falls \(\displaystyle p\) kein Teiler von \(\displaystyle a\) ist, folgt aus dem kleinen Fermatschen Satz, dass die rechte Seite der Gleichung ein Vielfaches der Primzahl \(\displaystyle p\) ist. Damit ist einer der Faktoren ein Teiler von \(\displaystyle p\).
Es gilt folglich
\(\displaystyle a^{(p-1)/2}\equiv \pm 1 \mod{p}\)

Verallgemeinerung

Man kann den kleinen fermatschen Satz zum Satz von Euler (Satz 164S) verallgemeinern.
Für zwei teilerfremde Zahlen \(\displaystyle n\) und \(\displaystyle a\) gilt
\(\displaystyle a^{\varphi (n)} \equiv 1 \pmod{n},\)
wobei \(\displaystyle \varphi(n)\) die Eulersche Phifunktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen 1 und \(\displaystyle n-1\), welche teilerfremd zu \(\displaystyle n\) sind. Ist \(\displaystyle n\) eine Primzahl, so ist \(\displaystyle \varphi(n)=n-1\), so dass man Fermats kleinen Satz als Spezialfall erhält.

Bemerkung

Aus der Gültigkeit der Kongruenz \(\displaystyle a^p \equiv a \pmod{p}\) für eine bestimmte Zahl \(\displaystyle a\) kann man nicht einfach schließen, dass \(\displaystyle p\) prim ist. Z. B. ist \(\displaystyle 4^{15} \equiv 4 \pmod{15}\), obwohl 15 keine Primzahl ist. Nichtprimzahlen, die diese Eigenschaft aufweisen, werden Fermatsche Pseudoprimzahlen genannt.

Die Mathematik muß man schon deswegen studieren, weil sie die Gedanken ordnet.

M. W. Lomonossow

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Kleiner fermatscher Satz; wb:Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Kleiner Satz von Fermat aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе