Euler-Jacobi pseudoprime checker
561 is an Euler–Jacobi pseudoprime to base 2: the power with exponent 280 leaves 1, matching its Jacobi symbol, although 561 is composite. Enter an odd composite number and a base to see each value behind the verdict. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 561
- A
- 2
- Gcd
- 1
- Jacobi
- 1
- Exponent
- 280
- Remainder
- 1
An Euler–Jacobi pseudoprime to a given base is an odd composite integer that obeys Euler's criterion as if it were prime. For a coprime base a, that means a raised to the power (n minus one) over two is congruent to the Jacobi symbol of a over n, modulo n. Every odd prime that does not divide a satisfies the same congruence, so composites that still pass are the interesting failures of a Solovay–Strassen style test. This checker is built for that exact question: given odd composite n and base a, decide whether n is an Euler–Jacobi pseudoprime to a.
What an Euler–Jacobi pseudoprime is, and how it differs from Fermat and Euler tests
Euler's criterion says that if p is an odd prime and a is not divisible by p, then a to the power (p minus one) over two is congruent to the Legendre symbol of a over p, modulo p. The Jacobi symbol (a/n) extends that quadratic character from odd primes to any odd positive integer n, so it is tempting to write the same congruence with n in place of p. When n is an odd prime the two symbols agree and the congruence is a theorem.
When n is odd and composite, the congruence may still hold for some bases even though n is not prime. Those n are called Euler–Jacobi pseudoprimes to base a, provided gcd(a, n) equals one. The condition is strictly stronger than the Fermat test a to the n minus one congruent to one modulo n, and it is also stronger than the weaker Euler test that only asks the modular power to be plus or minus one.
The classic illustration is three hundred forty-one to base two: it is a Fermat pseudoprime, the power two to the one hundred seventy is one modulo three hundred forty-one, but the Jacobi symbol (2/341) is minus one, so the Euler–Jacobi congruence fails. Five hundred sixty-one, the smallest Carmichael number, does satisfy the congruence for base two and is therefore an Euler–Jacobi pseudoprime to that base. Ninety-one to base ten is another standard classroom example that this checker confirms.
Where an Euler–Jacobi pseudoprime checker earns its keep
Number-theory courses and contest platforms use an Euler–Jacobi pseudoprime checker so learners can separate Fermat liars from Solovay–Strassen liars without implementing Jacobi reciprocity and modular exponentiation by hand. Research notebooks and recreational scans call the same contract when they want an independent oracle for a published list: five hundred sixty-one, one thousand one hundred five, one thousand seven hundred twenty-nine, and the other classic base-two examples should all return true, while three hundred forty-one to base two must return false.
Cryptography workshops that introduce the Solovay–Strassen primality test need a tool that refuses prime n, because the pedagogical point is the composite that mimics Euler's criterion, not a restatement that primes pass. Engineering teams that write property tests for their own Jacobi or modular-power libraries can pin this response as a cross-check.
Prefer this tool when the question is strictly whether a given odd composite satisfies the Euler–Jacobi congruence to a given base—not when you need a search over all bases, a Fermat-only test, a Miller–Rabin witness report, or certificates for multi-thousand-bit integers.
What you can do with it
Classroom checks of Solovay–Strassen liars
Let students submit n equals 561 with base 2 and confirm a true Euler–Jacobi flag, then contrast with 341 to base 2, which is only a Fermat liar.
Independent oracle for published tables
Validate offline lists of Euler–Jacobi pseudoprimes against a deterministic Jacobi-plus-modular-power implementation.
FAQ
What makes n an Euler–Jacobi pseudoprime to base a?
n must be odd and composite, gcd(a, n) must be 1, and a^((n−1)/2) must be congruent to the Jacobi symbol (a/n) modulo n.
Why are even n and prime n rejected?
Euler–Jacobi pseudoprimes are defined as odd composites that mimic Euler's criterion.
How is this different from a Fermat pseudoprime?
A Fermat pseudoprime to base a only needs a^{n−1} ≡ 1 (mod n). The Euler–Jacobi test also requires the modular square root of that Fermat condition to match the Jacobi symbol. 341 is a Fermat liar to base 2 but not an Euler–Jacobi pseudoprime to base 2.
Is 561 an Euler–Jacobi pseudoprime to base 2?
Yes. Raising 2 to the power 280 and dividing by 561 leaves 1, and the Jacobi symbol of 2 over 561 is also 1, so the congruence holds even though 561 is composite. It is the smallest Carmichael number.
What if the base shares a factor with the number?
Then the number is not an Euler–Jacobi pseudoprime to that base, because the definition requires the two to be coprime. The answer is no, and the common divisor is shown so you can see why.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your 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)Example request
{
"n": 561,
"a": 2
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.euler_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_abs | 9007199254740991 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
Even n and prime n are rejected with invalid_input rather than a misleading false flag, because the definition applies only to odd composites. The response reports the gcd, the Jacobi symbol, the modular power, whether the congruence holds, and a single boolean that is true only when the full definition is met. The same deterministic module runs free in the browser and on the API path at $0.002 per successful call.
What an Euler–Jacobi pseudoprime is, and how it differs from Fermat and Euler tests
The capability never calls a composite a prime and never calls a prime a pseudoprime: prime and even inputs are errors, and the boolean is_euler_jacobi_pseudoprime is true only when n is an admitted odd composite, the pair is coprime, and the full Jacobi congruence holds.
Input contract, response fields, and error behaviour
The criterion string restates a^((n-1)/2) ≡ (a/n) (mod n) so a page or notebook can show the definition next to the verdict. When gcd is greater than one, Jacobi is zero and the pair is not an Euler–Jacobi pair even if some accidental power vanishes. Example: n equals five hundred sixty-one and a equals two yields jacobi one, remainder one, and a true flag; n equals three hundred forty-one and a equals two yields jacobi minus one, remainder one, and a false flag. All arithmetic is exact BigInt; there is no floating point and no random witness. POST a JSON body with two required integers: n, the odd composite candidate (aliases modulus and number), and a, the base (alias base). Each field may arrive as a JSON number or as a decimal digit string; values must be whole integers whose absolute value stays within the JavaScript safe-integer range so that primality of n is decided by a fixed-witness Miller–Rabin set that is deterministic on that bound. Missing fields, fractions, booleans, empty strings, and oversized values fail with invalid_input naming the field. On success the body echoes n and a as numbers, reports gcd and the boolean coprime, returns jacobi in the set minus one, zero, or one, gives exponent as (n minus one) over two and remainder as a to that exponent modulo n, sets congruence_holds when remainder matches the Jacobi symbol reduced into the residue system modulo n, and sets is_euler_jacobi_pseudoprime only when the pair is coprime and the congruence holds.
Where an Euler–Jacobi pseudoprime checker earns its keep
Keep n odd and composite, treat invalid_input as a client fix, and pin remainder and jacobi in tests so a future refactor cannot silently change the modular result.
Integration use cases
Property tests for number-theory libraries
Pin gcd, Jacobi symbol, remainder, and the boolean in unit tests so a local reciprocity routine cannot drift from the definition.
Technical questions
What if gcd(a, n) is greater than one?
The pair is not an Euler–Jacobi pair. The response still returns gcd, jacobi 0, and the modular remainder, but is_euler_jacobi_pseudoprime is false because the definition requires coprimality.
What does the Euler–Jacobi pseudoprime checker cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.