Fermat Primality Test Calculator

Enter a number and a base to run the Fermat primality test.

How it is calculated

The tool computes the residue r = an−1 mod n using fast modular exponentiation, so large powers are never written out in full. The largest n it accepts is 9,007,199,254,740,992 (2⁵³); above that a number can no longer be held exactly. If r = 1 the verdict is Probably prime; any other value is proof that n is Composite. Both n and the base a must be whole numbers, n must be at least 4, and a must lie between 2 and n − 2; otherwise there is no result. If the base is left empty it uses 2. The verdict “Probably prime” is not a proof: composite numbers that pass for a given base are called Fermat pseudoprimes, so a second base should be tried.

Worked example

Test n = 341 with base a = 2. The tool needs 2340 mod 341. Since 210 = 1024 = 3 × 341 + 1, we have 210 ≡ 1 (mod 341), so 2340 = (210)34 ≡ 1. The residue is 1 and the verdict is Probably prime. But 341 = 11 × 31 is composite: it is a pseudoprime to base 2. Run the same n with base 3 and the residue is 56, which gives Composite and exposes it.

Try this example →

Common mistakes

  • Taking Probably prime as a proof of primality. 341 passes with base 2 yet equals 11 × 31, so always repeat with several bases such as 2, 3, 5 and 7.
  • Trying n = 1, 2 or 3, or a base outside 2 to n − 2. The tool returns nothing for these, since the theorem needs a base in that range.
  • Choosing a base that shares a factor with n. For n = 561 the base 3 gives a residue of 375 and is rejected, while the base 5 gives 1; a failing base is conclusive, a passing one is not.
  • Entering a decimal or a number with thousands separators. n and a must be plain whole numbers.
  • Thinking Carmichael numbers like 561 are caught by trying more bases. Any base coprime to n passes for them, so a different test is needed.

Sources

About this calculator

Fermat's little theorem states that if n is a prime number, then for any integer base a not divisible by n, a^(n-1) ≡ 1 (mod n). This calculator runs that check in reverse: given a number n and a chosen base a, it computes a^(n-1) mod n — if the result isn't 1, n is definitely composite; if it is 1, n is only probably prime, since rare composite numbers (Fermat pseudoprimes, and the especially stubborn Carmichael numbers) can pass the test for many bases; a Carmichael number passes for every base that shares no factor with n.

Because it's fast to compute even for large numbers, the Fermat test is used as a cheap first-pass filter in cryptography and computer science education — quickly discarding obvious composites before running slower, more rigorous primality tests like Miller-Rabin, which underpins real-world RSA key generation. It's also a standard exercise in number theory courses for illustrating modular exponentiation and the difference between a necessary and a sufficient condition for primality.

Was this helpful?

You can pick up to 3 reactions.

Note from the editors

A failed test is a certificate, a passed one is only a hint. Try 15 with the preset base 2: the residue is 4, not 1, which proves 15 is composite without finding any factor. Now try 17, the preset, where 2 to the 16th power leaves remainder 1. Teaching examples are a good fit for this tool. Which numbers do you test, and do you try several bases in a row?

Comments

  • Be the first to comment.

Popular calculators

All Calculators