How this instrument works
The Fermat primality test starts from the same identity behind Fermat's Little Theorem: for a genuinely prime n and any witness a not divisible by it, aⁿ⁻¹ mod n always comes out to 1. Turning that fact into a test means running the calculation in reverse — given some n whose status is unknown, compute aⁿ⁻¹ mod n and see what shows up. If the outcome is anything other than 1, the theorem has been directly contradicted, which can only happen when n is composite. That direction of the test is airtight: a non-1 result proves compositeness outright, no hedging required.
The other direction carries a real limitation, and this calculator is built to be upfront about it. A result of 1 is consistent with n being prime, but consistency is not proof. A handful of composite numbers, the Carmichael numbers, manage to satisfy aⁿ⁻¹ ≡ 1 (mod n) for every witness base coprime to them, sailing through the check while remaining thoroughly composite underneath. That means a 1 only ever means 'probably prime' here — a strong signal, backed by the fact that stray composites failing to be Carmichael numbers usually get caught by most witnesses, but never a certainty the way a non-1 result is.
This asymmetry is the entire point of the test, not a flaw hiding in the margins. Compositeness gets proved outright the moment a single witness fails; primality only ever accumulates evidence, one witness at a time, without ever closing the case completely. Software that needs an actual proof of primality reaches for other tools entirely — this sheet is built for the fast, honest, probabilistic screen the Fermat check has always been, not for a claim it was never designed to make.
- Enter the candidate you want to test into Number to test (n).
- Choose a base to test against and enter it into Witness base (a); 2 is the most common starting choice.
- Read Fermat test result: a value of 1 means n passed for this witness, and anything else proves n composite.
- Try a second or third Witness base against the same n — passing several witnesses strengthens, but never finalizes, the case for primality.
- Treat a non-1 result as decisive and a result of 1 as evidence, not as a certificate.
Worked example — testing 7 against the witness 2
Set Number to test (n) to 7 and Witness base (a) to 2. The sheet raises 2 to the power n minus 1, which is 6, giving 2^6 equals 64. Reducing 64 by 7 leaves a remainder of 1, since 7 times 9 is 63 and 64 minus 63 is 1 — so Fermat test result reads exactly 1, consistent with 7 genuinely being prime.
That single passing witness is evidence, not a certificate — with a number as small as 7, checking every witness base below it (or simply recognizing it has no divisors besides 1 and itself) closes the question completely, but this calculator only ever reports what one witness reveals. A far larger candidate passing the same test against 2 would carry the identical caveat: probably prime, not proven, since a Carmichael number could in principle pass this exact same check.
Questions
Does a Fermat test result of 1 prove that n is prime?
No — it only shows that n behaved the way a prime would for that one witness base. Certain composite numbers, called Carmichael numbers, pass aⁿ⁻¹ ≡ 1 (mod n) for every base coprime to them, so a result of 1 is honestly reported here as 'probably prime,' never as a proof. Genuine certainty about primality requires a different kind of test entirely, one built to close off that gap.
Why does a result other than 1 prove n is composite for certain?
Because Fermat's Little Theorem guarantees aⁿ⁻¹ ≡ 1 (mod n) whenever n is truly prime and a isn't a multiple of it — so any other outcome directly contradicts that guarantee, and the only way to contradict it is for n to not be prime. There is no equivalent loophole running this direction: a failed witness is conclusive, full stop, unlike a passed one.
What is a Carmichael number, and why does it matter here?
It is a composite number that passes the Fermat test against every witness base coprime to it, mimicking a genuine prime no matter which base is tried. Their existence is exactly why this test is described as probabilistic rather than a proof of primality — 561 is the smallest example, equal to 3 times 11 times 17, yet indistinguishable from a prime under this particular check.
Does testing more than one witness base make the result more trustworthy?
Yes, in practice, though not in an absolute sense — a composite number that isn't a Carmichael number typically fails for most witness bases, so passing several different ones lowers the odds of a false read considerably. It still falls short of certainty, since a true Carmichael number would pass every single witness offered to it without exception.
How is the Fermat test related to Fermat's Little Theorem?
It applies that theorem in the direction it was never guaranteed to run: the theorem states what a genuinely prime modulus does to a witness base, and this test instead uses the computed outcome to make an inference about an unknown candidate. That reversal is exactly where the test's honest limitation comes from — proving compositeness through contradiction works perfectly, but inferring primality from agreement never quite closes the loop.