www.wikidata.de-de.nina.az

Kleiner fermatscher Satz Der kleine fermatsche Satz kurz der kleine Fermat ist ein Lehrsatz der Zahlentheorie Er macht e

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 allgemeingültige Kongruenz:

wobei eine ganze Zahl und eine Primzahl ist (die weitere Symbolik wird im Artikel Kongruenz beschrieben).

Falls kein Vielfaches von ist, kann man das Resultat in die häufig benutzte Form

bringen, da dann das multiplikative Inverse modulo existiert.

Beweis Bearbeiten

Der Satz kann mit Induktion über bewiesen werden oder als Spezialfall des Satzes von Lagrange aus der Gruppentheorie aufgefasst werden. Dieser sagt, dass jedes Gruppenelement potenziert mit der (endlichen) Gruppenordnung das Einselement ergibt.

Siehe: Beweise des kleinen fermatschen Satzes im Beweisarchiv

Folgerung durch Euler Bearbeiten

Die 3. Binomische Formel besagt:

Sei nun eine ungerade Primzahl und eine beliebige ganze Zahl. Falls kein Teiler von ist, folgt aus dem kleinen fermatschen Satz, dass die rechte Seite der Gleichung ein Vielfaches der Primzahl ist. Damit ist einer der Faktoren ein Vielfaches von .

Es gilt folglich

Diese Folgerung wird Leonhard Euler zugeschrieben.

Verallgemeinerung Bearbeiten

Man kann den kleinen fermatschen Satz zum Satz von Euler verallgemeinern.

Für zwei teilerfremde Zahlen und gilt

wobei die eulersche φ-Funktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen und , welche teilerfremd zu sind. Ist eine Primzahl, so ist , so dass man Fermats kleinen Satz als Spezialfall erhält.

Anwendung als Primzahlentest Bearbeiten

Nach dem kleinen fermatschen Satz gilt für jede Primzahl und jedes dazu teilerfremde :

mit einer ganzen Zahl . Diese Beziehung kann auch für eine zusammengesetzte Zahl und eine Zahl mit zutreffen. Dies ist jedoch zumindest für große Zahlen sehr selten. Findet man Zahlen mit dieser Eigenschaft für eine zusammengesetzte Zahl , kann dies zur Faktorisierung der Zahl genutzt werden, da die Faktoren auf der linken Seite dann mit einer Wahrscheinlichkeit von 50 % echte Teiler von liefern.

Für eine Zahl mit 100 oder mehr Stellen ist eine Primfaktorzerlegung jedoch nur mit effizienteren Verfahren wie dem quadratischen Sieb möglich. Der Satz kann daher auch in seiner Umkehrung benutzt werden, um mit hoher Verlässlichkeit zu beurteilen, ob eine Zahl eine Primzahl ist. Bei großen Zahlen mit über 100 Stellen ist praktisch nicht daran zu zweifeln, dass eine Primzahl ist, falls die Gleichung für ein mit gilt. (siehe: Fermatscher Primzahltest)

Für einen exakten Beweis wäre allerdings die Prüfung aller Werte notwendig, so dass die Probedivision in diesem Fall effizienter ist. Es ist nicht bekannt, dass eine 100-stellige oder größere Zahl auf diese Weise faktorisiert werden konnte.

Für einige spezielle Zahlen können solche Ausnahmen allerdings häufiger gefunden werden.

Shor-Algorithmus Bearbeiten

Es sei das Produkt zweier großer Primzahlen und . Wir betrachten eine Zahl mit . Wir wissen, dass für den Exponenten

gilt.

Es stellt sich die Frage, ob diese Gleichung bereits für kleinere Exponenten erfüllt ist. Der Quantenteil des Shor-Algorithmus zur Faktorisierung großer Zahlen dient der Berechnung der kleinsten Zahl , für die diese Gleichung gilt. Der klassische Teil dieses Algorithmus kann leicht auf nahezu jedem Computer ausgeführt werden.

Wenn man die Potenzen einer Zahl bezüglich der Modulo-Operation betrachtet, wiederholen diese sich in Zyklen. Dies ist unvermeidlich, da nur die Werte angenommen werden können. Wir betrachten dies am Beispiel kleinerer Zahlen.

Wir können uns auf die Betrachtung von Primzahlen beschränken, da sich die minimale Zyklenlänge für das Produkt aus dem kleinsten gemeinsamen Vielfachen der Zyklenlängen für die Faktoren ergibt.

Beispiel mit p=7
n
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 aus berechnet. Um größere Zahlen zu vermeiden, kann man das Ergebnis einfacher aus berechnen.

In diesem Beispiel mit ergibt sich für folgender Zyklus der Werte

  • 1, 2, 4, 1, 2, 4, 1, 2, …

Für ergibt sich

  • 1, 3, 2, 6, 4, 5, 1, 3, …

Für alle drei Basen 2, 3 und 5 gilt zur Zahl 7

oder allgemein

für alle und alle natürlichen a, für die gilt . Dies ist eine unmittelbare Folge des kleinen Satzes von Fermat.

Am Beispiel der Modulo-Werte für sieht man, dass sich der Algorithmus verkürzen lässt, wenn der Zyklus kürzer ist. Da , ist auch , d. h. . Für größere Zahlen lässt sich so Arbeit einsparen.

Weitere Vereinfachung Bearbeiten

Hat die Form ergeben sich weitere Vereinfachungen der Berechnung. Dies wird hier am Beispiel verdeutlicht.

Beispiel mit p=17
n 1 2 4 8 16 32
2 4 16 1 1 1
3 9 13 16 1 1
5 8 13 16 1 1
7 15 4 16 1 1
11 2 4 16 1 1
13 16 1 1 1 1

Da ein Vielfaches der Zyklenlänge ist, kommen für nur die Zahlen in Betracht, was den Rechenaufwand vor allem für sehr große deutlich reduzieren kann. Noch weniger Arbeit macht der Fall

da das Ergebnis dann für die nächste Potenz von 2 schon als 1 feststeht.

Literatur Bearbeiten

Weblinks Bearbeiten

Wikibooks: Beweis zum kleinen Satz von Fermat – Lern- und Lehrmaterialien
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der kleine fermatsche Satz kurz der kleine Fermat ist ein Lehrsatz der Zahlentheorie Er macht eine Aussage uber die Eigenschaften von Primzahlen und wurde im 17 Jahrhundert von Pierre de Fermat aufgestellt Der Satz beschreibt die allgemeingultige Kongruenz a p a mod p displaystyle a p equiv a pmod p wobei a displaystyle a eine ganze Zahl und p displaystyle p eine Primzahl ist die weitere Symbolik wird im Artikel Kongruenz beschrieben Falls a displaystyle a kein Vielfaches von p displaystyle p ist kann man das Resultat in die haufig benutzte Form a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p bringen da dann das multiplikative Inverse a 1 displaystyle a 1 modulo p displaystyle p existiert Inhaltsverzeichnis 1 Beweis 2 Folgerung durch Euler 3 Verallgemeinerung 4 Anwendung als Primzahlentest 4 1 Shor Algorithmus 4 1 1 Weitere Vereinfachung 5 Literatur 6 WeblinksBeweis BearbeitenDer Satz kann mit Induktion uber a displaystyle a nbsp bewiesen werden oder als Spezialfall des Satzes von Lagrange aus der Gruppentheorie aufgefasst werden Dieser sagt dass jedes Gruppenelement potenziert mit der endlichen Gruppenordnung das Einselement ergibt Siehe Beweise des kleinen fermatschen Satzes im BeweisarchivFolgerung durch Euler BearbeitenDie 3 Binomische Formel besagt a p 1 2 1 a p 1 2 1 a p 1 1 displaystyle a frac p 1 2 1 cdot a frac p 1 2 1 a p 1 1 nbsp Sei nun p displaystyle p nbsp eine ungerade Primzahl und a displaystyle a nbsp eine beliebige ganze Zahl Falls p displaystyle p nbsp kein Teiler von a displaystyle a nbsp ist folgt aus dem kleinen fermatschen Satz dass die rechte Seite der Gleichung ein Vielfaches der Primzahl p displaystyle p nbsp ist Damit ist einer der Faktoren ein Vielfaches von p displaystyle p nbsp Es gilt folglich a p 1 2 1 mod p displaystyle a frac p 1 2 equiv pm 1 pmod p nbsp Diese Folgerung wird Leonhard Euler zugeschrieben Verallgemeinerung BearbeitenMan kann den kleinen fermatschen Satz zum Satz von Euler verallgemeinern Fur zwei teilerfremde Zahlen n displaystyle n nbsp und a displaystyle a nbsp gilt a f n 1 mod n displaystyle a varphi n equiv 1 pmod n nbsp wobei f n displaystyle varphi n nbsp die eulersche f Funktion bezeichnet Diese liefert die Anzahl der Zahlen zwischen 1 displaystyle 1 nbsp und n 1 displaystyle n 1 nbsp welche teilerfremd zu n displaystyle n nbsp sind Ist n displaystyle n nbsp eine Primzahl so ist f n n 1 displaystyle varphi n n 1 nbsp so dass man Fermats kleinen Satz als Spezialfall erhalt Anwendung als Primzahlentest BearbeitenNach dem kleinen fermatschen Satz gilt fur jede Primzahl p displaystyle p nbsp und jedes dazu teilerfremde a displaystyle a nbsp a p 1 2 1 a p 1 2 1 a p 1 1 k p displaystyle left a frac p 1 2 1 right cdot left a frac p 1 2 1 right a p 1 1 k cdot p nbsp mit einer ganzen Zahl k displaystyle k nbsp Diese Beziehung kann auch fur eine zusammengesetzte Zahl p displaystyle p nbsp und eine Zahl a displaystyle a nbsp mit 1 lt a lt p displaystyle 1 lt a lt p nbsp zutreffen Dies ist jedoch zumindest fur grosse Zahlen p displaystyle p nbsp sehr selten Findet man Zahlen a displaystyle a nbsp mit dieser Eigenschaft fur eine zusammengesetzte Zahl p displaystyle p nbsp kann dies zur Faktorisierung der Zahl p displaystyle p nbsp genutzt werden da die Faktoren auf der linken Seite dann mit einer Wahrscheinlichkeit von 50 echte Teiler von p displaystyle p nbsp liefern Fur eine Zahl p displaystyle p nbsp mit 100 oder mehr Stellen ist eine Primfaktorzerlegung jedoch nur mit effizienteren Verfahren wie dem quadratischen Sieb moglich Der Satz kann daher auch in seiner Umkehrung benutzt werden um mit hoher Verlasslichkeit zu beurteilen ob eine Zahl eine Primzahl ist Bei grossen Zahlen mit uber 100 Stellen ist praktisch nicht daran zu zweifeln dass p displaystyle p nbsp eine Primzahl ist falls die Gleichung fur ein a displaystyle a nbsp mit 1 lt a lt p displaystyle 1 lt a lt p nbsp gilt siehe Fermatscher Primzahltest Fur einen exakten Beweis ware allerdings die Prufung aller Werte 1 lt a lt p 1 displaystyle 1 lt a lt p 1 nbsp notwendig so dass die Probedivision in diesem Fall effizienter ist Es ist nicht bekannt dass eine 100 stellige oder grossere Zahl auf diese Weise faktorisiert werden konnte Fur einige spezielle Zahlen konnen solche Ausnahmen allerdings haufiger gefunden werden Shor Algorithmus Bearbeiten Es sei n displaystyle n nbsp das Produkt zweier grosser Primzahlen p displaystyle p nbsp und q displaystyle q nbsp Wir betrachten eine Zahl x displaystyle x nbsp mit 1 lt x lt n displaystyle 1 lt x lt n nbsp Wir wissen dass fur den Exponenten r f n p 1 q 1 displaystyle r varphi n p 1 cdot q 1 nbsp x r 1 mod n displaystyle x r equiv 1 pmod n nbsp gilt Es stellt sich die Frage ob diese Gleichung bereits fur kleinere Exponenten erfullt ist Der Quantenteil des Shor Algorithmus zur Faktorisierung grosser Zahlen dient der Berechnung der kleinsten Zahl r displaystyle r nbsp fur die diese Gleichung gilt Der klassische Teil dieses Algorithmus kann leicht auf nahezu jedem Computer ausgefuhrt werden Wenn man die Potenzen einer Zahl bezuglich der Modulo Operation betrachtet wiederholen diese sich in Zyklen Dies ist unvermeidlich da nur die Werte 1 2 3 n 1 displaystyle 1 2 3 ldots n 1 nbsp angenommen werden konnen Wir betrachten dies am Beispiel kleinerer Zahlen Wir konnen uns auf die Betrachtung von Primzahlen beschranken da sich die minimale Zyklenlange fur das Produkt aus dem kleinsten gemeinsamen Vielfachen der Zyklenlangen fur die Faktoren ergibt Beispiel mit p 7 n 2 n displaystyle 2 n nbsp 2 n mod 7 displaystyle 2 n pmod 7 nbsp 3 n displaystyle 3 n nbsp 3 n mod 7 displaystyle 3 n pmod 7 nbsp 5 n displaystyle 5 n nbsp 5 n mod 7 displaystyle 5 n pmod 7 nbsp 0 1 1 1 1 1 11 2 2 3 3 5 52 4 4 9 2 25 43 8 1 27 6 125 64 16 2 81 4 625 25 32 4 243 5 3125 36 64 1 729 1 15625 17 128 2 2187 3 78125 5und so weiter In der Tabelle wurde a n mod p displaystyle a n pmod p nbsp aus a n displaystyle a n nbsp berechnet Um grossere Zahlen zu vermeiden kann man das Ergebnis einfacher aus a a n 1 mod p displaystyle a cdot a n 1 pmod p nbsp berechnen In diesem Beispiel mit p 7 displaystyle p 7 nbsp ergibt sich fur a 2 displaystyle a 2 nbsp folgender Zyklus der Werte a n mod p displaystyle a n pmod p nbsp 1 2 4 1 2 4 1 2 Fur a 3 displaystyle a 3 nbsp ergibt sich 1 3 2 6 4 5 1 3 Fur alle drei Basen 2 3 und 5 gilt zur Zahl 7 a 7 1 c 1 mod 7 displaystyle a 7 1 cdot c equiv 1 pmod 7 nbsp fur alle c 1 displaystyle c geq 1 nbsp oder allgemein a p 1 c 1 mod p displaystyle a p 1 cdot c equiv 1 pmod p nbsp fur alle c 1 displaystyle c geq 1 nbsp und alle naturlichen a fur die gilt 1 lt a lt p displaystyle 1 lt a lt p nbsp Dies ist eine unmittelbare Folge des kleinen Satzes von Fermat Am Beispiel der Modulo Werte fur a 2 displaystyle a 2 nbsp sieht man dass sich der Algorithmus verkurzen lasst wenn der Zyklus kurzer ist Da 2 3 1 mod 7 displaystyle 2 3 equiv 1 pmod 7 nbsp ist auch 2 3 2 1 mod 7 displaystyle 2 3 2 equiv 1 pmod 7 nbsp d h 2 7 1 1 mod 7 displaystyle 2 7 1 equiv 1 pmod 7 nbsp Fur grossere Zahlen lasst sich so Arbeit einsparen Weitere Vereinfachung Bearbeiten Hat p displaystyle p nbsp die Form 2 n 1 displaystyle 2 n 1 nbsp ergeben sich weitere Vereinfachungen der Berechnung Dies wird hier am Beispiel p 17 displaystyle p 17 nbsp verdeutlicht Beispiel mit p 17 n 1 2 4 8 16 322 n mod 17 displaystyle 2 n pmod 17 nbsp 2 4 16 1 1 13 n mod 17 displaystyle 3 n pmod 17 nbsp 3 9 13 16 1 15 n mod 17 displaystyle 5 n pmod 17 nbsp 5 8 13 16 1 17 n mod 17 displaystyle 7 n pmod 17 nbsp 7 15 4 16 1 111 n mod 17 displaystyle 11 n pmod 17 nbsp 11 2 4 16 1 113 n mod 17 displaystyle 13 n pmod 17 nbsp 13 16 1 1 1 1Da p 1 2 4 displaystyle p 1 2 4 nbsp ein Vielfaches der Zyklenlange ist kommen fur r displaystyle r nbsp nur die Zahlen 2 4 8 16 displaystyle 2 4 8 16 nbsp in Betracht was den Rechenaufwand vor allem fur sehr grosse p displaystyle p nbsp deutlich reduzieren kann Noch weniger Arbeit macht der Fall x r 16 1 mod 17 displaystyle x r equiv 16 equiv 1 pmod 17 nbsp da das Ergebnis dann fur die nachste Potenz von 2 schon als 1 feststeht Literatur BearbeitenPeter Bundschuh Einfuhrung in die Zahlentheorie Springer Lehrbuch 6 uberarbeitete und aktualisierte Auflage Springer Verlag Berlin Heidelberg 2008 ISBN 978 3 540 76490 8 doi 10 1007 978 3 540 76491 5 Gunter Saake Kai Uwe Sattler Algorithmen und Datenstrukturen 4 Auflage S 657 Harald Scheid Zahlentheorie 3 Auflage Spektrum Akademischer Verlag Heidelberg Berlin 2003 ISBN 3 8274 1365 6 Waclaw Sierpinski Elementary Theory of Numbers Edited and with a preface by Andrzej Schinzel North Holland Mathematical Library Band 31 2 uberarbeitete und erweiterte Auflage North Holland u a Amsterdam u a 1988 ISBN 0 444 86662 0 MR0930670 Weblinks Bearbeiten nbsp Wikibooks Beweis zum kleinen Satz von Fermat Lern und Lehrmaterialien Eric W Weisstein Fermat s Little Theorem In MathWorld englisch Fermat s Little Theorem auf Cut the Knot Video Der kleine Satz von Fermat Padagogische Hochschule Heidelberg PHHD 2012 zur Verfugung gestellt von der Technischen Informationsbibliothek TIB doi 10 5446 19892 Abgerufen von https de wikipedia org w index php title Kleiner fermatscher Satz amp oldid 224975536