Kleiner Satz von Fermat
Geben Sie Basis und Modul ein und sehen Sie, ob a^(n−1) mod n gleich 1 ist: Bei 2 und 7 ist der Rest von 2^6 gleich 1, bei 2 und 15 dagegen 4. So prüfen Sie Hausaufgaben oder finden ein zusammengesetztes Gegenbeispiel. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Rechenbeispiel
- A
- 2
- N
- 7
- Ergebnis
- 1
- Erster Text
- 2
- N
- 7
- Exponent
- 6
Der kleine Satz von Fermat ist die klare Aussage der modularen Arithmetik: ist n prim und die Basis a nicht durch n teilbar, so ist a hoch n minus eins kongruent zu eins modulo n. Lernende, Tutorinnen und Tutoren sowie Entwicklerinnen und Entwickler brauchen ständig eine schnelle Auswertung genau dieses Potenzrestes—nicht eine Prosa-Zusammenfassung des Beweises—um Hausaufgaben zu prüfen, zusammengesetzte Gegenbeispiele zu testen oder modulare Routinen unit-zutesten. Dieser Prüfer für den kleinen Satz von Fermat nimmt die ganzen Zahlen a und n entgegen, lehnt das Paar ab, wenn gcd(a, n) nicht eins ist, und liefert sonst a^(n−1) mod n mit einem booleschen Flag, das Ihnen sagt, ob der Rest eins ist.
Was der kleine Satz von Fermat behauptet und was dieses Werkzeug berechnet
In der üblichen Lehrbuchform lautet der kleine Satz von Fermat: ist n eine Primzahl und a eine ganze Zahl, die nicht durch n teilbar ist, so ist a hoch n minus eins kongruent zu eins modulo n. Mit dem modularen Operator, den Programmierer täglich nutzen, heißt das: a^(n−1) mod n gleich 1, sobald diese Voraussetzungen gelten. Sie liefern die Basis a und den Modul n.
Der Prüfer verlangt zuerst, dass n eine ganze Zahl mindestens zwei ist, weil die modulare Reduktion mit einem Modul unter zwei kein nützlicher Unterrichtsvertrag ist. Anschließend verlangt er, dass der größte gemeinsame Teiler von a und n eins ist—die Teilerfremdheits-Hypothese, die bei primem n mit dem klassischen Wortlaut übereinstimmt (a nicht durch n teilbar) und bei zusammengesetztem n sinnvoll bleibt, wenn Sie erkunden wollen, was außerhalb der Satzgarantie geschieht.
Bestehen beide Prüfungen, führt die Engine binäre modulare Exponentiation (quadrieren und multiplizieren) über BigInt aus, sodass Zwischenprodukte exakt bleiben, auch wenn der Exponent n−1 groß ist.
Für Unterricht, Hausaufgaben und Gegenbeispiele
Lehrkräfte nutzen einen Prüfer für den kleinen Satz von Fermat, damit Lernende Handrechnungen von a^(p−1) mod p bei kleinen Primzahlen vor dem Beweis prüfen und absichtlich zusammengesetzte n ausprobieren, um zu sehen, dass der Rest nicht immer eins ist. Prüfungsgeneratoren und LMS-Plugins brauchen ein deterministisches Orakel, das nicht teilerfremde Eingaben ablehnt, statt stillschweigend einen Rest zu liefern, der Bewerter verwirrt.
Kryptographie-Kursnotizbücher brauchen oft einen einzigen exakten modularen Potenzschritt, wenn Spielzeug-RSA-Schlüssel eingeführt werden oder erklärt wird, warum der Exponent n−1 in der elementaren Zahlentheorie erscheint, bevor Eulers Satz die Geschichte mit φ(n) verallgemeinert. Wenn Sie später Eulers Satz mit φ(n), modulare Inverse oder chinesische Restsatz-Zerlegungen brauchen, rufen Sie jene getrennten Fähigkeiten auf; diese bleibt die dedizierte Fermat-Landing a^(n−1) mod n, damit Suchabsicht und Antwortform klar bleiben.
Anwendungsfälle
Unit-Tests für modulare Potenzierung
Skripte pinnen bekannte Reste wie 2^6 mod 7 = 1 und 2^14 mod 15 = 4, ohne BigInt square-and-multiply in jeder Sprache neu zu implementieren.
Häufige Fragen
Warum muss gcd(a, n) gleich 1 sein?
Der kleine Satz von Fermat gilt für Basen, die zum Modul teilerfremd sind (äquivalent: nicht durch die Primzahl n teilbar).
Beweist ein Ergebnis 1, dass n prim ist?
Nein. Ist n prim und gcd(a,n)=1, ist der Rest immer 1, doch Zusammengesetzte können für manche Basen ebenfalls 1 liefern. Nutzen Sie dafür ein eigenes Primheitswerkzeug.
Wie prüfe ich den kleinen Satz von Fermat mit Basis 2 und Modul 7?
Geben Sie 2 als Basis und 7 als Modul ein. Das Werkzeug rechnet 2 hoch 6, teilt durch 7 und liefert den Rest 1: Der Satz gilt für diese Primzahl, wie erwartet.
Warum ergibt 2^14 mod 15 den Wert 4 und nicht 1?
Weil 15 keine Primzahl ist und der Satz dann nichts garantiert. Die Basis 2 hat mit 15 keinen gemeinsamen Teiler, also berechnet das Werkzeug den Rest von 2 hoch 14 und erhält 4: 15 besteht den Test nicht.
Kann ich eine negative Basis oder einen sehr großen Modul verwenden?
Ja. Eine negative Basis wird zuerst modulo n reduziert, und der Modul muss nur eine ganze Zahl von mindestens 2 sein. Die Potenz entsteht durch wiederholtes Quadrieren und Multiplizieren mit exakten ganzen Zahlen, daher bleibt der Rest auch bei riesigen Exponenten exakt.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem Stack
curl -X POST https://api.kit.forhosting.com/numth/fermat-little-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"n":7}'const res = await fetch("https://api.kit.forhosting.com/numth/fermat-little-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"n": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/fermat-little-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"n": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/fermat-little-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"n":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"n":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/fermat-little-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"a": 2,
"n": 7
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.fermat_little_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Dieselbe reine BigInt-Logik speist das kostenlose Browser-Werkzeug und den kostenpflichtigen API-Pfad zu $0.002 pro erfolgreicher Anfrage, sodass Klassendemonstrationen und Produktionsskripte nie über einen Rest streiten.
Was der kleine Satz von Fermat behauptet und was dieses Werkzeug berechnet
Der Beweis ist nicht das Produkt dieses Endpoints; das Produkt ist der exakte Rest jener Potenz. Die Antwort spiegelt a und n als Dezimalstrings, meldet den Exponenten n−1, den nichtnegativen Rest result, gcd als die Zeichenkette "1", ein boolesches congruent_to_one, das genau dann wahr ist, wenn result gleich 1 ist, und einen kurzen expression-String, den Sie neben die Antwort drucken können. Klassische Primprüfung: a gleich 2 und n gleich 7 ergibt 2^6 mod 7 gleich 1, also ist congruent_to_one wahr. Klassische zusammengesetzte Sonde: a gleich 2 und n gleich 15 ergibt 2^14 mod 15 gleich 4, also ist congruent_to_one falsch—genau die Art Gegenbeispiel, die zeigt, dass a^(n−1) ≡ 1 allein kein Primheitszertifikat ist.
Eingabevertrag, Fehler und Lesen der Antwort
Ist n kleiner als zwei, scheitert die Aufgabe mit der Meldung, der Modul müsse mindestens zwei sein. Ist gcd(a, n) nicht eins, scheitert die Aufgabe mit einer Meldung, die den gcd nennt—zum Beispiel gcd(2, 4) gleich 2—damit Aufrufer wissen, dass das Paar außerhalb der Teilerfremdheits-Hypothese liegt, statt zu raten, warum die Potenz nicht berechnet wurde. Negative Basen werden akzeptiert und vor dem Potenzieren in das nichtnegative Restsystem modulo n reduziert, passend zur Standard-Modulararithmetik. Senden Sie per POST einen JSON-Körper mit zwei Pflicht-Ganzzahlfeldern: a (Alias base) und n (Alias modulus, mod). Jedes Feld darf eine JSON-Zahl oder ein dezimaler Ganzzahlstring sein; die Stringform ist bevorzugt, wenn Werte den sicheren Ganzzahlbereich von JavaScript verlassen. Brüche, leere Strings, nichtnumerische Token und Werte mit mehr als vierundsechzig Dezimalziffern scheitern mit invalid_input und werden nie berechnet. Bei Erfolg ist jedes numerische Feld im Körper ein Dezimalstring außer congruent_to_one, das boolesch ist, sodass große Ganzzahlen ohne Präzisionsverlust durch JSON laufen. Koppeln Sie diesen Prüfer mit einem separaten Faktorisierungs- oder Primheitswerkzeug, wenn Ihr Ablauf mehr als den Potenzrest braucht; dieser Endpoint beantwortet nur a^(n−1) mod n unter dem Teilerfremdheits-Tor, damit die SEO-Absicht klar und die Antwort minimal bleibt. Der Preis ist ein fester $0.002 pro erfolgreicher Anfrage auf der Einheit item; fehlgeschlagene Validierung wird nicht berechnet.
Klassendemonstrationen, zusammengesetzte Sonden und API-Automatisierung
Entwicklerinnen und Entwickler koppeln die API an Property-Tests, die a^(n−1) ≡ 1 für zufällige Basen teilerfremd zu einem bekannten Primmodul behaupten, oder an Regressionssuiten, die bekannte zusammengesetzte Gegenbeispiele wie 2^14 mod 15 gleich 4 festhalten. Halten Sie a und n innerhalb der veröffentlichten Zifferngrenze, pinnen Sie in Tests den String-form-result und das Flag congruent_to_one, und Sie erhalten reproduzierbare Reste für Hausaufgaben, Tutorenplattformen und Edge-Worker, ohne ein vollständiges Computeralgebrasystem aufzusetzen.
Integrationsbeispiele
FLT-Prüfungen für Hausaufgaben und Unterricht
Lernende geben Basis a und Primzahl n ein, um a^(n−1) mod n = 1 zu bestätigen, oder testen zusammengesetzte n, um zu sehen, wann der Rest nicht 1 ist.
LMS- und Prüfungs-Orakel für Auto-Bewertung
Bewerten Sie modulare Arithmetik-Aufgaben mit deterministischem Rest und lehnen Sie nicht teilerfremde Paare als ungültig ab, statt ein Erfolgs-Payload zu erfinden.
Technische Fragen
Was berechnet dieser Prüfer für den kleinen Satz von Fermat?
Bei ganzen Zahlen a und n mit n ≥ 2 und gcd(a,n)=1 liefert er a^(n−1) mod n sowie, ob dieser Rest 1 ist (congruent_to_one).
Was geschieht, wenn n zusammengesetzt ist?
Der Prüfer berechnet weiterhin a^(n−1) mod n, wenn gcd(a,n)=1. congruent_to_one kann wahr oder falsch sein; falsche Fälle sind nützliche Unterrichts-Gegenbeispiele.
Was kostet der Prüfer für den kleinen Satz von Fermat?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen das vorausbezahlte KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingaben werden nie berechnet.