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)

ap≡amod  p,a^p \equiv a \mod{p},
wobei aa eine ganze Zahl und pp eine Primzahl ist.
Falls aa kein Vielfaches von pp ist, kann man das Resultat in die häufig benutzte Form
ap−1≡1mod  pa^{p-1} \equiv 1 \mod{p}
bringen.

Beweis

Wir müssen zeigen, dass p∣(ap−a)p|(a^p-a) ist.
Mittels vollständiger Induktion über aa ergibt sich:
Induktionsanfang: 0p−0=00^p-0=0 ist durch pp teilbar.
Induktionsschritt: Sei nun p∣(ap−a)p|(a^p-a). Nach dem binomischen Satz gilt:
(a+1)p−(a+1)=ap+(p1)ap−1+…+(pp−1)a+1−(a+1)(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 pp teilbar, denn in der Darstellung
(pk)=p⋅(p−1)⋯(p−k+1)1⋅2⋯k{\chooseNT p k}=\dfrac{p\cdot(p-1)\cdots(p-k+1)}{1\cdot2\cdots k}
taucht pp für 1≤k≤p1\leq k\leq p nur im Zähler auf. Damit folgt : (a+1)p−(a+1)≡ap+1−(a+1)(a+1)^p-(a+1)\equiv a^p+1-(a+1) ≡ap−amod  p\equiv a^p-a\mod p, und nach Induktionsvoraussetzung ist das ≡0\equiv0.
Für a<0a<0 und p=2p=2 ist die Behauptung trivial, da a2=(−a)2a^2=(-a)^2. Für p>2p>2 gilt - da alle pp dann ungerade sind:
ap−a=−∣a∣p+∣a∣=−(∣a∣p−∣a∣)a^p-a=- |a|^p+|a|=-(|a|^p-|a|)
Nun ist wegen dem oben Bewiesen aber pp Teiler der rechten Seite. □\qed

Bemerkung

In obigen Beweis wurde gleichzeitig die Behauptung
p∣ (pk)p|\, \chooseNT p k
für pp prim und 1≤k≤p−11\leq k\leq p-1 gezeigt. Mit dem binomischen Satz gilt dann
(a+b)p≡ap+bpmod  p(a+b)^p\equiv a^p +b^p \mod p

Folgerung durch Euler

Ist pp eine ungerade Primzahl, so gilt für eine beliebige ganze Zahl aa.
(a(p−1)/2−1)⋅(a(p−1)/2+1)=ap−1−1(a^{(p-1)/2}-1) \cdot (a^{(p-1)/2}+1) = a^{p-1} - 1
Falls pp kein Teiler von aa ist, folgt aus dem kleinen Fermatschen Satz, dass die rechte Seite der Gleichung ein Vielfaches der Primzahl pp ist. Damit ist einer der Faktoren ein Teiler von pp.
Es gilt folglich
a(p−1)/2≡±1mod  pa^{(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 nn und aa gilt
aφ(n)≡1(modn),a^{\varphi (n)} \equiv 1 \pmod{n},
wobei φ(n)\varphi(n) die Eulersche Phifunktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen 1 und n−1n-1, welche teilerfremd zu nn sind. Ist nn eine Primzahl, so ist φ(n)=n−1\varphi(n)=n-1, so dass man Fermats kleinen Satz als Spezialfall erhält.

Bemerkung

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

Jede mathematische Formel in einem Buch halbiert die Verkaufszahl dieses Buches.

Stephen Hawking

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е
Datenschutzerklärung

 

Zahlentheorie