Rechner zum kleinen Satz von Fermat

Prüfe die Standardform und alternative Form des kleinen Satzes von Fermat mit schneller modularer Potenzierung.

Eine Fermat-Kongruenz berechnen

Gib eine ganzzahlige Basis und einen Primzahlmodulus ein und wähle die Form des Satzes.

Basiszahl (a)

Primzahl (p)

Form des Satzes

Über den kleinen Satz von Fermat

Der kleine Satz von Fermat verbindet Primzahlen, Potenzen und modulare Arithmetik. Seine Standardform besagt: Ist p prim und a nicht durch p teilbar, dann lässt a^(p - 1) bei Division durch p den Rest 1. In Kongruenzschreibweise ist a^(p - 1) kongruent zu 1 modulo p. Für a = 2 und p = 7 gilt 2^6 = 64, und 64 lässt bei Division durch 7 den Rest 1. Eine gleichwertige Form besagt, dass a^p für jede ganze Zahl a kongruent zu a modulo p ist, sofern p prim ist. Diese Version umfasst auch den Fall, dass p die Zahl a teilt, denn dann haben beide Seiten den Rest null. Die Standardform verlangt, dass der größte gemeinsame Teiler von a und p gleich 1 ist. Der Rechner prüft Primzahleigenschaft und Teilerfremdheit vor der Auswertung der gewählten Kongruenz. Die direkte Berechnung einer großen Potenz kann riesige Zwischenwerte erzeugen. Deshalb nutzt das Werkzeug binäre modulare Potenzierung, auch wiederholtes Quadrieren genannt. Es quadriert die aktuelle Basis wiederholt und reduziert nach jeder Multiplikation modulo p. So bleibt der exakte Rest erhalten, die unhandliche vollständige Potenz wird vermieden, und die Zahl der Schritte wächst nur logarithmisch mit dem Exponenten. Die Methode ist grundlegend für praktische Kryptografiesoftware. Der Satz kann beweisen, dass eine Zahl zusammengesetzt ist: Scheitert die Kongruenz für eine teilerfremde Basis, kann der vorgeschlagene Modulus nicht prim sein. Ein bestandener Fermat-Test beweist jedoch keine Primzahleigenschaft. Manche zusammengesetzten Zahlen bestehen ihn für bestimmte Basen; Carmichael-Zahlen bestehen den Standardtest sogar für jede zu ihnen teilerfremde Basis. Zuverlässige Primzahltests verwenden daher stärkere deterministische Prüfungen oder Verfahren wie Miller-Rabin mit sorgfältig ausgewählten Basen. Fermats Ergebnis unterstützt viele Bereiche der Zahlentheorie und Informatik. Es hilft, Exponenten in modularen Rechnungen zu verkleinern, motiviert Primzahltests und trägt zu den mathematischen Grundlagen der Public-Key-Kryptografie bei. RSA beruht unmittelbarer auf dem verwandten Satz von Euler, doch Fermats Satz erklärt das zugrunde liegende Verhalten bei Primzahlmoduln. Modulare Inverse lassen sich außerdem mit a^(p - 2) modulo p finden, wenn p prim und a modulo p ungleich null ist. Verwende diesen Rechner zur Prüfung von Unterrichtsbeispielen und zum Erkunden modularer Muster, nicht zur Zertifizierung großer kryptografischer Primzahlen. Eingaben sind für verlässliche Primzahlprüfungen auf sichere JavaScript-Ganzzahlen begrenzt; die Potenzierung selbst nutzt exakte Ganzzahlarithmetik. Ein erfolgreiches Ergebnis bestätigt, dass gewählte Primzahl und Basis die ausgewählte Form erfüllen. Es belegt für sich allein nicht, dass ein ungeprüfter zusammengesetzter Kandidat prim ist.

Beispiele zum kleinen Satz von Fermat

Jedes Beispiel reduziert eine Potenz, ohne ihren vollständigen Wert zu bilden.

Eingaben und Form	Rest	Einordnung
a = 2, p = 7, Standard	2^6 mod 7 = 1	Die Standardkongruenz wird bestätigt.
a = 3, p = 11, Standard	3^10 mod 11 = 1	Ein klassisches Beispiel mit Primzahlmodulus.
a = 5, p = 13, alternativ	5^13 mod 13 = 5	Die alternative Form liefert den Rest der Basis.
a = 17, p = 17, alternativ	17^17 mod 17 = 0	Die alternative Form gilt auch, wenn p die Zahl a teilt.

So verwendest du den Satz-Rechner

Gib eine ganze Zahl größer als 1 als Basis a ein.
Gib eine Primzahl als Modulus p ein.
Wähle die Standardform für teilerfremde Eingaben oder die alternative Form für eine beliebige ganzzahlige Basis.
Wähle Satz berechnen, um die Potenz mittels modularer Potenzierung auszuwerten.
Prüfe den Rest und die Bestätigungsmeldung.

Häufige Fragen zum kleinen Satz von Fermat

Was bedeutet modulo p?

Modulo p bedeutet, Zahlen anhand ihrer Reste bei Division durch p zu vergleichen. Zwei Zahlen sind kongruent modulo p, wenn diese Reste übereinstimmen.

Warum muss p eine Primzahl sein?

Die Primzahleigenschaft ist eine notwendige Voraussetzung des kleinen Satzes von Fermat. Zusammengesetzte Moduln erfüllen die Kongruenz nicht durchgehend, auch wenn manche ausgewählte Tests bestehen.

Was unterscheidet die beiden Formen des Satzes?

Die Standardform liefert 1 und verlangt, dass a zu p teilerfremd ist. Die alternative Form liefert denselben Rest wie a und gilt für jede ganze Zahl a, sofern p prim ist.

Beweist ein bestandener Fermat-Test, dass eine Zahl prim ist?

Nein, manche zusammengesetzten Zahlen bestehen Fermat-Tests für bestimmte Basen. Ein gescheiterter Test beweist Zusammengesetztheit; nach einem bestandenen Test sind stärkere Primzahlprüfungen für Gewissheit nötig.

Wie funktioniert schnelle modulare Potenzierung?

Sie zerlegt den Exponenten in binäre Potenzen und quadriert die Basis wiederholt. Die Reduktion nach jeder Multiplikation hält die Werte klein und bewahrt den exakten Rest.