Anwendungen des Satzes von Fermat

Wenn eine natürliche Zahl pp eine Primzahl ist, dann gilt z. B. für a=2a=2
2p−1≡1 (modp) 2^{p-1} \equiv 1 \ \pmod{p}\,
Wenn der Satz außerdem für alle Basen bb kleiner als pp (1<b<p1 <b < p) gilt, also
bp−1≡1 (modp),b^{p-1} \equiv 1 \ \pmod{p},
dann ist die Zahl pp eine Primzahl. Um festzustellen, ob pp prim ist, muss man jedoch nicht alle natürlichen Zahlen bb kleiner pp durchtesten, sondern nur diejenigen davon, die Primzahlen sind.
Dieses Verfahren ist in dieser Form allerdings sehr langsam und aufwändig, wenn elektronische Hilfsmittel zur Verfügung stehen, ist das Testen auf Primzahlen über die Teilbarkeit im Allgemeinen schneller.

Beispiel

Wenn man die Potenzen einer Zahl bezüglich der Modulo-Operation betrachtet, bekommt man gewisse Zyklen:
Beispiel: p = 7
nn 2n2^n 2nmod  72^n\mod 7 3n3^n 3nmod  73^n\mod 7 5n5^n 5nmod  75^n\mod 7
0 1 1 1 1 1 1
1 2 2 3 3 5 5
2 4 4 9 2 25 4
3 8 1 27 6 125 6
4 16 2 81 4 625 2
5 32 4 243 5 3125 3
6 64 1 729 1 15625 1
7 128 2 2187 3 78125 5
und so weiter. In der Tabelle wurde anmod  pa^n\mod{p} aus ana^n berechnet. Um größere Zahlen zu vermeiden, kann man das Ergebnis einfacher aus a⋅(an−1mod  p)a \cdot (a^{n-1}\mod{p}) berechnen.
In diesem Beispiel mit p=7p=7 ergibt sich für a=2a=2 folgender Zyklus der Werte anmod  pa^n\mod{p}
  • 1, 2, 4, 1, 2, 4, 1, 2, ...
Für a=3a=3 ergibt sich
  • 1, 3, 2, 6, 4, 5, 1, 3, ...
Für alle drei Basen 2, 3 und 5 gilt zur Zahl 7 folgende Regel
a(7−1)∗c≡1 (mod7)a^{(7-1)*c} \equiv 1 \ \pmod{7} für alle c≥1c \geq 1
oder allgemein
a(p−1)∗c≡1 (modp)a^{(p-1)*c} \equiv 1 \ \pmod{p}
für alle c≥1c \geq 1 und alle natürlichen aa, für die gilt 1<a<p1 < a < p.
Am Beispiel der Modulo-Werte für a=2a=2 sieht man, dass sich der Algorithmus verkürzen lässt, wenn der Zyklus kürzer ist. Da 23mod  7=12^3\mod{7}=1 ist auch 23∗2mod  7=12^{3*2}\mod{7}=1, d. h. 27−1mod  7=12^{7-1}\mod{7}=1. Für größere Zahlen lässt sich so Arbeit einsparen.
Weitere Vereinfachung für p=2n+1p=2^{n+1} Hat pp die Form 2n+12^{n+1} ergeben sich weitere Vereinfachungen der Berechnung:
Beispiel: p = 17
n 1 2 4 8 16 32
2nmod  172^n\mod 17 2 4 16 1 1 1
3nmod  173^n\mod 17 3 9 13 16 1 1
5nmod  175^n\mod 17 5 8 13 16 1 1
7nmod  177^n\mod 17 7 15 4 16 1 1
11nmod  1711^n\mod 17 11 2 4 16 1 1
13nmod  1713^n\mod 17 13 16 1 1 1 1
Diese Tabelle zeigt z. B., dass man das Ergebnis für 216mod  172^{16} \mod{17} aus dem Wert für 242^4 ablesen kann, was den Rechenaufwand vor allem für sehr große pp deutlich reduzieren kann. Noch weniger Arbeit macht 131613^{16}, da sich das Ergebnis schon aus 13213^2 ergibt.
 
 

Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch.

Bertrand Russell

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Kleiner fermatscher Satz 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

 

Elementare Zahlentheorie