Fermat pseudoprime checker for any base
The Fermat pseudoprime checker takes a composite integer n and a base a, computes the exact residue of a raised to n minus one modulo n, and reports whether that residue is one.
Run — free
A passing composite is a Fermat pseudoprime to the selected base: it behaves like a prime under this particular test even though it is not prime. The checker also reports the greatest common divisor, making the result easier to inspect and explain.
What a passing result actually means
Fermat's little theorem says that if n is prime and a is not divisible by n, then a raised to the power n minus one leaves residue one modulo n. The converse is not guaranteed. Some composite integers also produce residue one for particular bases, and those composites are called Fermat pseudoprimes to those bases. This checker deliberately requires n to be composite, verifies that condition first, and then evaluates the congruence exactly. When passes_fermat_test and is_fermat_pseudoprime are true, the result means the supplied composite fooled Fermat's test for that specific base. It does not mean n is prime, probably prime, or a pseudoprime for every base. The base is part of the claim and should always accompany the result. The returned residue provides the direct arithmetic evidence: one is a pass, while any other value is a failure. The greatest common divisor is included because a nontrivial divisor immediately explains many failures and helps distinguish coprime-base experiments from inputs that already reveal a factor relationship.
How the calculation stays exact
Both inputs are decimal strings so integers larger than JavaScript's safe numeric range are not rounded before calculation. The accepted range ends at the largest unsigned 64-bit integer, which gives the primality check a clear, enforceable boundary. Before running Fermat's test, the checker uses a deterministic Miller–Rabin procedure with a witness set proven sufficient across that entire range. A detected prime causes an input error because prime numbers satisfy Fermat's theorem but cannot, by definition, be pseudoprimes. For a valid composite, modular exponentiation uses repeated squaring rather than constructing the enormous value a^(n-1). Every multiplication is reduced modulo n, so intermediate values remain bounded and exact under BigInt arithmetic. Euclid's algorithm computes gcd(a,n) separately. The base must satisfy 2 <= a <= n - 2, avoiding trivial residue classes and keeping the question aligned with the standard elementary Fermat test. No random witnesses, clock values, network calls, or floating-point operations affect the answer, so identical inputs always produce identical output.
Using the checker in study and verification workflows
A classic first example is n = 341 with base a = 2. Since 341 is composite but 2^340 is congruent to one modulo 341, it passes and is a Fermat pseudoprime to base two. Change the base and the same composite may fail, which is why a single Fermat test is not a general-purpose primality certificate. In a lesson, the structured output can connect the definition directly to the computed residue. In a test suite, it can preserve known pseudoprime and non-pseudoprime vectors without relying on a mathematics package or machine-dependent number conversions. In exploratory work, compare several allowed bases while keeping n fixed to see how strongly the choice of witness matters. Treat a true result as a demonstration of the limitation of Fermat's test, not as permission to accept the number as prime in cryptographic or security-sensitive code. The API price is $0.002 per checked pair, while the browser version can perform the same deterministic computation locally.
What you can do with it
Demonstrate a classic pseudoprime
Verify that a known composite such as 341 passes Fermat's congruence for base 2 and inspect the exact residue.
Build number-theory exercises
Check answer keys for problems that ask whether a specified composite is a pseudoprime to a specified base.
Test arithmetic implementations
Use deterministic structured results as reference vectors for modular-exponentiation or educational primality-test code.
FAQ
What makes n a Fermat pseudoprime to base a?
It must be composite and satisfy a^(n-1) congruent to 1 modulo n for the supplied base.
Why does the checker reject prime n?
Primes normally pass Fermat's congruence, but the term pseudoprime applies only to composite integers, so accepting a prime would answer a different question.
Does a true result prove that n is prime?
No. The checker already establishes that n is composite. A true result demonstrates precisely how that composite fools Fermat's test for one base.
Why are n and a entered as strings?
Decimal strings preserve every digit through the API and browser, including values above the safe integer range of ordinary JavaScript numbers.
What does it cost?
The API costs $0.002 per checked pair. The browser runner performs the same calculation locally.
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/fermat-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"341","a":"2"}'const res = await fetch("https://api.kit.forhosting.com/numth/fermat-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "341",
"a": "2"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/fermat-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "341",
"a": "2"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/fermat-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"341","a":"2"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"341","a":"2"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/fermat-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": "341",
"a": "2"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.fermat_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_digits | 20 |
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. |