Der kleine Satz von Fermat - Fermat's little theorem

Der kleine Satz von Fermat besagt, dass, wenn p eine Primzahl ist , für jede ganze Zahl a die Zahl a ^p − a ein ganzzahliges Vielfaches von p ist . In der Notation der modularen Arithmetik wird dies ausgedrückt als

${\displaystyle a^{p}\equiv a{\pmod {p}}.}$

Wenn beispielsweise a = 2 und p = 7, dann ist 2 ⁷ = 128 und 128 − 2 = 126 = 7 × 18 ein ganzzahliges Vielfaches von 7.

Wenn a nicht durch p teilbar ist , ist der kleine Satz von Fermat äquivalent zu der Aussage, dass a ^{p − 1} − 1 ein ganzzahliges Vielfaches von p ist , oder in Symbolen:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

Ist beispielsweise a = 2 und p = 7, dann ist 2 ⁶ = 64 und 64 − 1 = 63 = 7 × 9 also ein Vielfaches von 7.

Der kleine Satz von Fermat ist die Grundlage für den Fermat-Primalitätstest und ist eines der grundlegenden Ergebnisse der elementaren Zahlentheorie . Der Satz ist nach Pierre de Fermat benannt , der ihn 1640 aufgestellt hat. Er wird "kleiner Satz" genannt, um ihn von Fermats letztem Satz zu unterscheiden .

Geschichte

Pierre de Fermat

Pierre de Fermat stellte das Theorem erstmals in einem Brief vom 18. Oktober 1640 an seinen Freund und Vertrauten Frénicle de Bessy fest . Seine Formulierung entspricht der folgenden:

Wenn p eine Primzahl und a eine beliebige ganze Zahl ist, die nicht durch p teilbar ist , dann ist a ^{p − 1} − 1 durch p teilbar .

Fermats ursprüngliche Aussage war

Tout nombre Premier mesure infailliblement une des puissances de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre Premier donné ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la uraufführung satisfont tout de même à la question.${\displaystyle -1}$${\displaystyle -1}$

Dies kann übersetzt werden, wobei Erklärungen und Formeln zum besseren Verständnis in Klammern hinzugefügt werden, als:

Jede Primzahl [ p ] teilt notwendigerweise eine der Kräfte minus eins jede [geometrischen] Progression [ a , a ² , a ³ , ... ] [das heißt, es existiert t derart , daß p dividieren a ^t - 1 ], und der Exponent dieser Potenz [ t ] teilt die gegebene Primzahl minus eins [dividiert p – 1 ]. Nachdem man die erste Potenz [ t ] gefunden hat, die die Frage erfüllt, erfüllen alle diejenigen, deren Exponenten Vielfache des Exponenten des ersten sind, in ähnlicher Weise die Frage [dh alle Vielfachen des ersten t haben die gleiche Eigenschaft].

Fermat hat den Fall, in dem a ein Vielfaches von p ist, weder betrachtet noch seine Behauptung bewiesen, sondern nur festgestellt:

Et cette proposition est généralement vraie en toutes progressions et en tous nombres Premiers; de quoi je vous envoierois la demonstration, si je n'appréhendois d'être trop long.

(Und dieser Satz gilt im Allgemeinen für alle Reihen [ sic ] und für alle Primzahlen; ich würde Ihnen eine Demonstration davon schicken, wenn ich nicht Angst hätte, zu lange weiterzumachen.)

Euler lieferte den ersten veröffentlichten Beweis 1736 in einem Papier mit dem Titel "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" in den Proceedings of the St. Petersburg Academy, aber Leibniz hatte praktisch den gleichen Beweis in einem unveröffentlichten Manuskript aus einer Zeit vor 1683 geliefert.

Der Begriff "Fermats kleiner Satz" wurde wahrscheinlich erstmals 1913 in der Zahlentheorie von Kurt Hensel drucktechnisch verwendet :

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleinen Satz genannt zu Fermat gepflegt werden, weil ein ganz spezieller erster von Fermat bewiesen ist.

(In jeder endlichen Gruppe gibt es einen fundamentalen Satz, der gewöhnlich als kleiner Satz von Fermat bezeichnet wird, weil Fermat der erste war, der einen ganz besonderen Teil davon bewiesen hat.)

Eine frühe Verwendung in englischer Sprache erfolgt in AA Albert ‚s Moderne Höhere Algebra (1937), die‚die so genannte bezieht sich ‚kleine‘ Fermat‘auf 206 Seite.

Weitere Geschichte

Einige Mathematiker stellten unabhängig voneinander die verwandte Hypothese auf (manchmal fälschlicherweise als chinesische Hypothese bezeichnet), dass 2 ^p ≡ 2 (mod p ) genau dann gilt, wenn p eine Primzahl ist. Tatsächlich ist der "wenn"-Teil wahr, und es ist ein Spezialfall von Fermats kleinem Satz. Der "nur wenn"-Teil ist jedoch falsch: Zum Beispiel 2 ³⁴¹ ≡ 2 (mod 341) , aber 341 = 11 × 31 ist eine Pseudoprimzahl . Siehe unten .

Beweise

Mehrere Beweise des kleinen Satzes von Fermat sind bekannt. Es wird häufig als Korollar des Satzes von Euler bewiesen .

Verallgemeinerungen

Der Satz von Euler ist eine Verallgemeinerung des kleinen Satzes von Fermat: Für jeden Modul n und jede ganze Zahl eine zu n teilerfremde Zahl , gilt

${\displaystyle a^{\varphi (n)}\äquiv 1{\pmod {n}},}$

wobei φ ( n ) die Totient-Funktion von Euler bezeichnet (die die ganzen Zahlen von 1 bis n zählt , die zu n teilerfremd sind ). Der kleine Satz von Fermat ist in der Tat ein Sonderfall, denn wenn n eine Primzahl ist, dann gilt φ ( n ) = n − 1 .

Eine logische Folge der Eulerschen Theorems ist: für jede positive ganze Zahl n , wenn die ganze Zahl a ist coprime mit n dann

${\displaystyle x\equiv y{\pmod {\varphi (n)}}\quad {\text{impliziert}}\quad a^{x}\equiv a^{y}{\pmod {n}},}$

für beliebige ganze Zahlen x und y . Dies folgt aus dem Satz von Euler, denn wenn , dann x = y + kφ ( n ) für eine ganze Zahl k , und man hat ${\displaystyle x\äquiv y{\pmod {\varphi(n)}}}$

${\displaystyle a^{x}=a^{y+\varphi (n)k}=a^{y}(a^{\varphi (n)})^{k}\äquiv a^{y}1^ {k}\equiv a^{y}{\pmod {n}}.}$

Wenn n eine Primzahl ist, ist dies auch ein Korollar des kleinen Satzes von Fermat. Dies wird häufig in der modularen Arithmetik verwendet , da dies eine Reduzierung der modularen Exponentiation mit großen Exponenten auf Exponenten kleiner als n ermöglicht .

Wenn n keine Primzahl ist, wird dies in der Public-Key-Kryptographie verwendet , typischerweise im RSA-Kryptosystem wie folgt: if

${\displaystyle y=x^{e}{\pmod {n}},}$

Abrufen von x aus den Werten e und n ist einfach , wenn man weiß , φ ( n ) . Tatsächlich erlaubt der erweiterte euklidische Algorithmus die Berechnung des modularen Inversen von e modulo φ ( n ) , also der ganzen Zahl f so . Es folgt dem ${\displaystyle ef\equiv 1{\pmod {\varphi(n)}}}$

${\displaystyle x\equiv x^{ef}\equiv (x^{e})^{f}\equiv y^{f}{\pmod {n}}.}$

Ist dagegen n = pq das Produkt zweier verschiedener Primzahlen, dann gilt φ ( n ) = ( p − 1)( q − 1) . In diesem Fall ist das Auffinden von f aus n und e genauso schwierig wie das Berechnen von φ ( n ) (dies ist nicht bewiesen, aber es ist kein Algorithmus bekannt, um f zu berechnen, ohne φ ( n ) zu kennen ). Wenn man nur n kennt , hat die Berechnung von φ ( n ) im Wesentlichen die gleiche Schwierigkeit wie die Faktorisierung von n , da φ ( n ) = ( p − 1)( q − 1) , und umgekehrt sind die Faktoren p und q die ( ganzzahlige) Lösungen der Gleichung x ² – ( n − φ ( n ) + 1) x + n = 0 .

Die Grundidee des RSA-Kryptosystems ist also: Wenn eine Nachricht x als y = x ^e (mod n ) verschlüsselt wird , unter Verwendung öffentlicher Werte von n und e , dann kann sie nach derzeitigem Wissen nicht entschlüsselt werden, ohne das (geheime) Faktoren p und q von n .

Der kleine Satz von Fermat hängt auch mit der Carmichael-Funktion und dem Satz von Carmichael sowie mit dem Satz von Lagrange in der Gruppentheorie zusammen .

Umgekehrt

Die Umkehrung des kleinen Satzes von Fermat ist im Allgemeinen nicht richtig, da sie für Carmichael-Zahlen versagt . Es ist jedoch eine etwas stärkere Form des Theorems wahr, die als Lehmer-Theorem bekannt ist. Der Satz lautet wie folgt:

Falls es eine ganze Zahl a gibt, so dass

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

und für alle Primzahlen q Teilungs p - 1 hat man

${\displaystyle a^{(p-1)/q}\not \equiv 1{\pmod {p}},}$

dann ist p prim.

Dieses Theorem bildet die Grundlage für den Lucas-Primalitätstest , einen wichtigen Primalitätstest , und Pratts Primalitätszertifikat .

Pseudoprimzahlen

Wenn a und p teilerfremde Zahlen sind, so dass a ^{p −1} − 1 durch p teilbar ist , dann muss p keine Primzahl sein. Ist dies nicht der Fall , so heißt p eine (Fermat-)Pseudoprimzahl zur Basis a . Die erste Pseudoprimzahl zur Basis 2 wurde 1820 von Pierre Frédéric Sarrus gefunden : 341 = 11 × 31.

Eine Anzahl p , die eine Fermat pseudoprim zu Base wird ein für jede Zahl a coprime bis p ist eine sogenannte Carmichael Anzahl (zB 561). Alternativ kann jede Zahl p, die die Gleichheit erfüllt

${\displaystyle \gcd\left(p,\sum_{a=1}^{p-1}a^{p-1}\right)=1}$

ist entweder eine Primzahl oder eine Carmichael-Zahl.

Miller-Rabin-Primalitätstest

Der Miller-Rabin-Primalitätstest verwendet die folgende Erweiterung des kleinen Satzes von Fermat:

Wenn p eine ungerade Primzahl ist , und p - 1 = 2 ^s d mit d ungerade ist , dann ist jede für eine Primzahl p , entweder einer ^d ≡ 1 mod p , oder es existiert t derart , daß 0 ≤ t <s und a ^{2 t d} ≡ −1 mod p .

Dieses Ergebnis lässt sich aus dem kleinen Satz von Fermat daraus ableiten, dass, wenn p eine ungerade Primzahl ist, die ganzen Zahlen modulo p einen endlichen Körper bilden , in dem 1 genau zwei Quadratwurzeln 1 und −1 hat.

Der Miller-Rabin - Test verwendet diese Eigenschaft in der folgenden Art und Weise: Da p = 2 ^s d + 1 , mit d ungerade ist , eine ungerade ganze Zahl , für die Primalität getestet werden muß, wählen zufällig ein , so dass 1 < a < p ; dann berechne b = a ^d mod p ; wenn b weder 1 noch −1 ist, quadrieren Sie es wiederholt modulo p, bis Sie 1, −1 erhalten oder s- mal quadriert haben. Wenn b ≠ 1 und −1 nicht erhalten wurde, dann ist p nicht prim. Andernfalls kann p eine Primzahl sein oder nicht. Wenn p keine Primzahl ist, ist die Wahrscheinlichkeit, dass dies durch den Test bewiesen wird, größer als 1/4. Daher ist nach k nicht schlüssigen Zufallstests die Wahrscheinlichkeit, dass p keine Primzahl ist , kleiner als (3/4) ^k und kann somit durch Erhöhen von k beliebig klein gemacht werden .

Zusammenfassend beweist der Test entweder, dass eine Zahl keine Primzahl ist, oder behauptet, dass sie eine Primzahl mit einer beliebig niedrigen Fehlerwahrscheinlichkeit ist. Der Test ist sehr einfach zu implementieren und rechnerisch effizienter als alle bekannten deterministischen Tests. Daher wird es im Allgemeinen verwendet, bevor ein Primalitätsbeweis gestartet wird.

Siehe auch

Anmerkungen

Verweise

• Albert, A. Adrian (2015) [1938], Moderne höhere Algebra , Cambridge University Press , ISBN 978-1-107-54462-8
• Burton, David M. (2011), Die Geschichte der Mathematik / Eine Einführung (7. Aufl.), McGraw-Hill, ISBN 978-0-07-338315-6
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2. Aufl.), Lexington: DC Heath and Company , LCCN  77171950
• Mahoney, Michael Sean (1994), The Mathematical Career of Pierre de Fermat, 1601–1665 (2. Aufl.), Princeton University Press, ISBN 978-0-691-03666-3
• Ore, Oystein (1988) [1948], Zahlentheorie und ihre Geschichte , Dover, ISBN 978-0-486-65620-5
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elemente der Zahlentheorie , Englewood Cliffs: Prentice Hall , LCCN  71081766

Weiterlesen

• Paulo Ribenboim (1995). Das neue Buch der Primzahlaufzeichnungen (3. Aufl.). New York: Springer-Verlag. ISBN  0-387-94457-5 . S. 22–25, 49.

Externe Links

• Medien im Zusammenhang mit Fermats kleinem Theorem bei Wikimedia Commons
• János Bolyai und die Pseudoprimzahlen (auf Ungarisch)
• Der kleine Satz von Fermat im Schnitt
• Euler-Funktion und Satz bei Cut-the-Knot
• Fermats kleiner Satz und Sophies Beweis
• "Der kleine Satz von Fermat" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Der kleine Satz von Fermat" . MathWorld .
• Weisstein, Eric W. "Der kleine Satz von Fermat umgekehrt" . MathWorld .