Euler-Jacobi-Pseudoprimzahl-Pruefer
561 ist eine Euler–Jacobi-Pseudoprimzahl zur Basis 2: Die Potenz mit Exponent 280 lässt den Rest 1, passend zum Jacobi-Symbol, obwohl 561 zusammengesetzt ist. Geben Sie Zahl und Basis ein und sehen Sie jeden Wert hinter dem Ergebnis. 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
- N
- 561
- A
- 2
- Gcd
- 1
- Jacobi-Symbol
- 1
- Exponent
- 280
- Rest
- 1
Eine Euler–Jacobi-Pseudoprimzahl zu einer gegebenen Basis ist eine ungerade zusammengesetzte ganze Zahl, die Eulers Kriterium erfüllt, als wäre sie prim. Für eine zu n teilerfremde Basis a bedeutet das: a hoch (n minus eins) durch zwei ist kongruent zum Jacobi-Symbol von a über n, modulo n. Jede ungerade Primzahl, die a nicht teilt, erfüllt dieselbe Kongruenz; zusammengesetzte Zahlen, die trotzdem durchkommen, sind die interessanten Fehlschläge eines Tests im Stil von Solovay–Strassen. Dieser Prüfer beantwortet genau diese Frage: gegeben ungerades zusammengesetztes n und Basis a, ist n eine Euler–Jacobi-Pseudoprimzahl zu a?
Was eine Euler–Jacobi-Pseudoprimzahl ist und wie sie sich von Fermat- und Euler-Tests unterscheidet
Eulers Kriterium besagt: Ist p eine ungerade Primzahl und a nicht durch p teilbar, so ist a hoch (p minus eins) durch zwei kongruent zum Legendre-Symbol von a über p, modulo p. Das Jacobi-Symbol (a/n) erweitert diesen quadratischen Charakter von ungeraden Primzahlen auf jede ungerade positive ganze Zahl n, daher liegt es nahe, dieselbe Kongruenz mit n anstelle von p zu schreiben. Ist n eine ungerade Primzahl, stimmen beide Symbole überein und die Kongruenz ist ein Satz.
Ist n ungerade und zusammengesetzt, kann die Kongruenz für manche Basen trotzdem gelten, obwohl n nicht prim ist. Solche n heißen Euler–Jacobi-Pseudoprimzahlen zur Basis a, sofern gcd(a, n) gleich eins ist. Die Bedingung ist strikt stärker als der Fermat-Test (a hoch n minus eins kongruent zu eins modulo n) und auch stärker als der schwache Euler-Test, der nur verlangt, dass die Modularpotenz plus eins oder minus eins ist.
Das klassische Beispiel ist dreihunderteinundvierzig zur Basis zwei: es ist eine Fermat-Pseudoprimzahl, zwei hoch einhundertsiebzig ist eins modulo dreihunderteinundvierzig, aber das Jacobi-Symbol (2/341) ist minus eins, also scheitert die Euler–Jacobi-Kongruenz. Fünfhunderteinundsechzig, die kleinste Carmichael-Zahl, erfüllt die Kongruenz zur Basis zwei und ist daher eine Euler–Jacobi-Pseudoprimzahl zu dieser Basis. Einundneunzig zur Basis zehn ist ein weiteres Unterrichtsbeispiel, das dieser Prüfer bestätigt.
Wo ein Euler–Jacobi-Pseudoprimzahl-Prüfer seinen Nutzen hat
Zahlentheorie-Kurse und Wettbewerbsplattformen nutzen einen Euler–Jacobi-Pseudoprimzahl-Prüfer, damit Lernende Fermat-Lügner von Solovay–Strassen-Lügnern trennen, ohne Jacobi-Reziprozität und Modularpotenzierung von Hand zu implementieren. Forschungsnotebooks und Freizeit-Scans rufen denselben Vertrag auf, wenn sie ein unabhängiges Orakel für eine veröffentlichte Liste wollen: fünfhunderteinundsechzig, eintausendeinhundertfünf, eintausendsiebenhundertneunundzwanzig und die übrigen klassischen Beispiele zur Basis zwei sollen wahr liefern, während dreihunderteinundvierzig zur Basis zwei falsch liefern muss. Kryptographie-Workshops, die den Solovay–Strassen-Primzahltest vorstellen, brauchen ein Werkzeug, das primes n ablehnt, weil der didaktische Punkt die zusammengesetzte Zahl ist, die Eulers Kriterium nachahmt, nicht die Wiederholung, dass Primzahlen bestehen.
Ingenieurteams, die Eigenschaftstests für eigene Jacobi- oder Modularpotenz-Bibliotheken schreiben, können diese Antwort als Gegenprobe festnageln. Bevorzugen Sie dieses Werkzeug, wenn die Frage strikt lautet, ob eine gegebene ungerade zusammengesetzte Zahl die Euler–Jacobi-Kongruenz zu einer gegebenen Basis erfüllt — nicht wenn Sie eine Suche über alle Basen, einen reinen Fermat-Test, einen Miller–Rabin-Zeugenbericht oder Zertifikate für mehrtausendbitige ganze Zahlen brauchen.
Anwendungsfälle
Unterrichtsprüfungen von Solovay–Strassen-Lügnern
Lassen Sie Lernende n gleich 561 mit Basis 2 einreichen und ein wahres Euler–Jacobi-Flag bestätigen, dann kontrastieren Sie mit 341 zur Basis 2, das nur ein Fermat-Lügner ist.
Unabhängiges Orakel für veröffentlichte Tabellen
Prüfen Sie Offline-Listen von Euler–Jacobi-Pseudoprimzahlen gegen eine deterministische Jacobi-plus-Modularpotenz-Implementierung.
Häufige Fragen
Was macht n zu einer Euler–Jacobi-Pseudoprimzahl zur Basis a?
n muss ungerade und zusammengesetzt sein, gcd(a, n) muss 1 sein, und a^((n−1)/2) muss zum Jacobi-Symbol (a/n) modulo n kongruent sein.
Warum werden gerade n und prime n abgewiesen?
Euler–Jacobi-Pseudoprimzahlen sind definiert als ungerade Zusammengesetzte, die Eulers Kriterium nachahmen.
Worin unterscheidet sich das von einer Fermat-Pseudoprimzahl?
Eine Fermat-Pseudoprimzahl zur Basis a braucht nur a^{n−1} ≡ 1 (mod n). Der Euler–Jacobi-Test verlangt zusätzlich, dass die modulare Quadratwurzel dieser Fermat-Bedingung mit dem Jacobi-Symbol übereinstimmt. 341 ist ein Fermat-Lügner zur Basis 2, aber keine Euler–Jacobi-Pseudoprimzahl zur Basis 2.
Ist 561 eine Euler–Jacobi-Pseudoprimzahl zur Basis 2?
Ja. 2 hoch 280 geteilt durch 561 lässt den Rest 1, und das Jacobi-Symbol von 2 über 561 ist ebenfalls 1. Die Kongruenz gilt also, obwohl 561 zusammengesetzt ist; sie ist die kleinste Carmichael-Zahl.
Was ist, wenn Basis und Zahl einen gemeinsamen Faktor haben?
Dann ist die Zahl zu dieser Basis keine Euler–Jacobi-Pseudoprimzahl, weil die Definition Teilerfremdheit verlangt. Die Antwort lautet nein, und der gemeinsame Teiler wird angezeigt, damit Sie den Grund sehen.
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/euler-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":561,"a":2}'const res = await fetch("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 561,
"a": 2
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/euler-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 561,
"a": 2
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":561,"a":2}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":561,"a":2}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/euler-pseudoprime-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
{
"n": 561,
"a": 2
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.euler_pseudoprime_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.
Limits
max_abs | 9007199254740991 |
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
Gerade oder prime n werden mit invalid_input abgewiesen statt eines irreführenden Falsch-Negativs, denn die Definition gilt nur für ungerade Zusammengesetzte. Die Antwort liefert den gcd, das Jacobi-Symbol, die Modularpotenz, ob die Kongruenz gilt, und ein Boolean, das nur dann wahr ist, wenn die volle Definition erfüllt ist. Dasselbe deterministische Modul läuft kostenlos im Browser und auf dem API-Pfad zu $0.002 pro erfolgreichem Aufruf.
Was eine Euler–Jacobi-Pseudoprimzahl ist und wie sie sich von Fermat- und Euler-Tests unterscheidet
Die Fähigkeit nennt niemals eine zusammengesetzte Zahl prim und niemals eine Primzahl eine Pseudoprimzahl: prime oder gerade Eingaben sind Fehler, und das Boolean is_euler_jacobi_pseudoprime ist nur dann wahr, wenn n eine zugelassene ungerade zusammengesetzte Zahl ist, das Paar teilerfremd ist und die volle Jacobi-Kongruenz gilt.
Eingabevertrag, Antwortfelder und Fehlerverhalten
Die Zeichenkette criterion wiederholt a^((n-1)/2) ≡ (a/n) (mod n), damit eine Seite oder ein Notizbuch die Definition neben dem Urteil zeigen kann. Ist gcd größer als eins, ist Jacobi null und das Paar ist kein Euler–Jacobi-Paar, selbst wenn eine zufällige Potenz verschwindet. Beispiel: n gleich fünfhunderteinundsechzig und a gleich zwei liefert jacobi eins, remainder eins und ein wahres Flag; n gleich dreihunderteinundvierzig und a gleich zwei liefert jacobi minus eins, remainder eins und ein falsches Flag. Die gesamte Arithmetik ist exaktes BigInt; es gibt weder Gleitkomma noch einen zufälligen Zeugen. Senden Sie per POST einen JSON-Körper mit zwei Pflichtganzzahlen: n, dem ungeraden zusammengesetzten Kandidaten (Aliase modulus und number), und a, der Basis (Alias base). Jedes Feld darf als JSON-Zahl oder als Dezimalziffernkette ankommen; die Werte müssen ganze Zahlen sein, deren Betrag im sicheren JavaScript-Integerbereich bleibt, damit die Primzahleigenschaft von n durch eine feste Miller–Rabin-Zeugenmenge entschieden wird, deterministisch auf dieser Schranke. Fehlende Felder, Brüche, Booleans, leere Zeichenketten und zu große Werte scheitern mit invalid_input unter Nennung des Feldes. Bei Erfolg spiegelt der Körper n und a als Zahlen, liefert gcd und das Boolean coprime, gibt jacobi in der Menge minus eins, null oder eins zurück, setzt exponent auf (n minus eins) durch zwei und remainder auf a hoch diesem Exponenten modulo n, setzt congruence_holds, wenn remainder mit dem ins Restsystem modulo n reduzierten Jacobi-Symbol übereinstimmt, und setzt is_euler_jacobi_pseudoprime nur, wenn das Paar teilerfremd ist und die Kongruenz gilt.
Wo ein Euler–Jacobi-Pseudoprimzahl-Prüfer seinen Nutzen hat
Weil die Fähigkeit reines Parse der Stufe A ist, ist jeder erfolgreiche Aufruf deterministisch, offline und mit $0.002 bepreist, ohne Modell-Tokens. Halten Sie n ungerade und zusammengesetzt, behandeln Sie invalid_input als Korrektur auf Kundenseite und nageln Sie remainder und jacobi in Tests fest, damit eine spätere Umgestaltung das Modularergebnis nicht stillschweigend ändert.
Integrationsbeispiele
Eigenschaftstests für zahlentheoretische Bibliotheken
Nageln Sie gcd, Jacobi-Symbol, remainder und das Boolean in Unit-Tests fest, damit eine lokale Reziprozitätsroutine nicht von der Definition abdriftet.
Technische Fragen
Was geschieht, wenn gcd(a, n) größer als eins ist?
Das Paar ist kein Euler–Jacobi-Paar. Die Antwort liefert weiterhin gcd, jacobi 0 und den Modularrest, aber is_euler_jacobi_pseudoprime ist falsch, weil die Definition Teilerfremdheit verlangt.
Was kostet der Euler–Jacobi-Pseudoprimzahl-Prüfer?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen das vorausbezahlte KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingabe wird nicht berechnet.