Fermat Primality Test Explained

Fermat Primality Test Calculator

Number to test (n) Enter a positive integer greater than 3.

Base (a) Use a base from 2 through n − 2.

The Fermat primality test checks whether a number behaves the way a prime number should under Fermat's little theorem. For a chosen base a and candidate n, the central test is:

aⁿ⁻¹ ≡ 1 (mod n)

If the congruence fails, n is definitely composite. If it passes, the result is weaker: the number may be prime, or it may be a composite number that happens to pass for that base. That one-sided certainty is the defining feature of the Fermat test.

Passing the Fermat test is not a proof of primality. A failed test proves compositeness, but a passed test only says that the chosen base did not expose a contradiction.

Why Fermat's Little Theorem Leads to a Primality Test

Fermat's little theorem states that if p is prime and a is not divisible by p, then:

a^p−1 ≡ 1 (mod p)

This gives a necessary behavior for primes. Replace p with an unknown integer n, choose a base a, and test the same congruence. If the remainder is anything other than 1, n cannot be prime.

The reverse statement does not follow. A number can satisfy the congruence without being prime. This is why the logic runs in only one safe direction:

Prime → passes

When the theorem's conditions hold, a prime number satisfies the Fermat congruence.

Passes ↛ prime

A composite number can also produce remainder 1 for a chosen base.

The Fermat Test, Step by Step

1. Choose an integer n > 3 and a base 2 ≤ a ≤ n − 2.

↓

2. Compute gcd(a, n).

↓

3. If gcd(a, n) > 1, n is composite.

↓

4. Otherwise compute aⁿ⁻¹ mod n.

↓

5. Remainder ≠ 1 means composite. Remainder = 1 means the number passes for this base.

The wording in the final step matters. A correct implementation should return passes Fermat test, not simply prime.

Pseudocode

FermatTest(n, a)if n <= 1: return not primeif gcd(a, n) > 1: return compositer = modularExponentiation(a, n - 1, n)if r != 1: return compositereturn passes Fermat test

Examples That Show Both Sides of the Test

A composite number that fails immediately: n = 15, a = 2

For 15 and base 2:

2¹⁴ mod 15 = 4

The remainder is 4 rather than 1. Therefore, 15 is composite. Base 2 has exposed the failure.

A prime that passes: n = 17, a = 3

Since 17 is prime and 3 is coprime to 17, Fermat's little theorem applies:

3¹⁶ mod 17 = 1

The result matches the behavior required of a prime. This is consistent with 17 being prime, but the Fermat result alone is not the reason 17 is known to be prime.

Fermat Witnesses, Liars, and Pseudoprimes

The test becomes easier to reason about once three terms are separated.

Terms used in Fermat primality testing
Term	Meaning
Fermat witness	A base a for which aⁿ⁻¹ mod n is not 1, proving that n is composite.
Fermat liar	A base that gives remainder 1 even though n is composite.
Fermat pseudoprime to base a	A composite n that passes the Fermat test for the stated base a.

A pseudoprime is therefore base-dependent. A composite number may fool one base and fail another.

Why 341 Is a Classic False Positive

The number 341 is composite:

341 = 11 × 31

Yet base 2 gives:

2³⁴⁰ mod 341 = 1

So 341 passes the Fermat test to base 2. In this setting, 2 is a Fermat liar and 341 is a Fermat pseudoprime to base 2.

Changing the base exposes the problem:

3³⁴⁰ mod 341 = 56

Because 56 ≠ 1, base 3 is a Fermat witness for 341. The same candidate can therefore pass one Fermat test and fail another.

341 shows why multiple bases can help. A different base may find a witness that the first base missed. The next limitation is harder: some composite numbers pass for every base that is coprime to them.

Carmichael Numbers Are the Main Limitation

A Carmichael number is a composite integer n for which the Fermat congruence holds for every base a that is coprime to n:

aⁿ⁻¹ ≡ 1 (mod n) whenever gcd(a, n) = 1

This is much more troublesome than an ordinary base-specific pseudoprime. Trying another coprime base does not expose the number through the basic Fermat congruence.

Why 561 defeats ordinary Fermat testing

The smallest Carmichael number is 561:

561 = 3 × 11 × 17

It is plainly composite, yet coprime bases such as 2, 5, and 10 all satisfy:

Fermat test results for 561
Base a	gcd(a, 561)	a⁵⁶⁰ mod 561	Fermat result
2	1	1	Pass
5	1	1	Pass
10	1	1	Pass

Repeating the same kind of Fermat check with more coprime bases cannot repair this defect. There are infinitely many Carmichael numbers, so this is not a one-off curiosity.

Why the GCD Check Comes First

The condition gcd(a, n) = 1 is not a minor detail. If the chosen base shares a nontrivial factor with n, the greatest common divisor already proves that n is composite.

For example, choose n = 561 and a = 3:

gcd(3, 561) = 3

No modular exponentiation is needed. The factor 3 settles the primality question immediately.

Useful implementation rule: compute gcd(a, n) before the exponentiation. A nontrivial gcd gives stronger information than a Fermat pass or failure because it directly reveals a factor.

Why Repeating Fermat Tests Has No Universal Error Guarantee

For an ordinary composite number such as 341, testing several bases can improve the chance of finding a witness. It is tempting to turn that into a simple statement such as “more rounds always make the error probability tiny.” Fermat testing does not support that claim for every composite input.

A Carmichael number passes for every coprime base. If the random base selection keeps landing on coprime values, additional Fermat rounds continue to return 1. The failure is structural, not merely bad luck with one base.

This is one reason stronger probable-prime tests are preferred when large-number primality must be screened efficiently.

Efficient Modular Exponentiation

A Fermat implementation should not first construct the full value of aⁿ⁻¹ and then divide it by n. That intermediate number becomes enormous even for modest inputs.

Instead, binary modular exponentiation repeatedly squares values and reduces them modulo n along the way. The calculation keeps only residues that matter:

result = 1 base = a mod n exponent = n - 1while exponent > 0: if exponent is odd: result = (result × base) mod nbase = (base × base) mod n exponent = floor(exponent / 2)

This changes the practical cost of the exponentiation. The number of squaring steps grows with the number of bits in the exponent rather than with the exponent itself.

Why Carmichael Numbers Have This Behavior

Korselt's criterion gives a clean characterization. A composite integer n is a Carmichael number when it is square-free and, for every prime divisor p of n:

p − 1 divides n − 1

For 561, the prime divisors are 3, 11, and 17. Their predecessor values are 2, 10, and 16, and each divides 560. The structure of 561 therefore forces the Fermat congruence to hold for every base coprime to 561.

Small Carmichael numbers and their prime factorizations
Carmichael number	Prime factorization
561	3 × 11 × 17
1105	5 × 13 × 17
1729	7 × 13 × 19
2465	5 × 17 × 29
2821	7 × 13 × 31
6601	7 × 23 × 41

Fermat Test vs Trial Division and Miller–Rabin

How common primality methods differ
Method	What it checks	What a failure proves	Main limitation
Trial division	Looks for divisors up to a chosen bound, often through √n for a full small-number test.	A divisor proves compositeness.	Direct divisor search becomes costly as numbers grow.
Fermat test	Checks aⁿ⁻¹ ≡ 1 (mod n) for selected bases.	A failed congruence proves compositeness.	Pseudoprimes and Carmichael numbers can pass.
Miller–Rabin	Uses the factorization of n − 1 into 2^sd and tests stronger modular conditions.	A witness proves compositeness.	A probabilistic run needs enough rounds or a proven deterministic base set for the intended range.

Why Miller–Rabin goes further

Fermat testing checks only the final congruence aⁿ⁻¹ ≡ 1 (mod n). Miller–Rabin also examines intermediate modular squaring behavior after writing:

n − 1 = 2^sd, with d odd

Those extra conditions reject many composites that look prime to the basic Fermat test, including the Carmichael behavior that makes plain Fermat testing unreliable as a stand-alone primality decision.

Where the Fermat Test Is Still Useful

The Fermat test remains useful when its result is interpreted correctly. It provides a compact way to study modular arithmetic, Fermat's little theorem, compositeness witnesses, pseudoprimes, and the reason stronger primality tests exist.

It can also serve as an early compositeness screen: one witness is enough to reject a candidate. What it should not do is turn a passing result into an unsupported declaration that a number is prime.

For a direct prime-or-composite result rather than a base-dependent Fermat experiment, use the Prime Number Checker. Keeping the two results separate makes the distinction visible: the Fermat tool shows how a chosen base behaves, while a primality checker answers the actual classification question.

Common Implementation Errors

Returning “prime” after one passing base

A pass means only that the selected base did not prove compositeness. The correct label is passes Fermat test or probable prime under this test, not a proof of prime status.

Skipping gcd(a, n)

A shared factor can prove compositeness before modular exponentiation begins. Ignoring the GCD check throws away useful information.

Using trivial or poorly chosen bases

Base 1 carries no useful discriminating information. Base n − 1 is also weak for odd candidates because it behaves like −1 modulo n and can satisfy the congruence for reasons unrelated to primality. Restricting practical tests to 2 through n − 2 avoids those trivial endpoints.

Computing the full power first

Building aⁿ⁻¹ as a normal integer and taking the remainder afterward wastes time and memory. Modular exponentiation keeps each intermediate value bounded by the modulus.

Assuming more Fermat rounds defeat Carmichael numbers

More bases can expose ordinary pseudoprimes, but coprime-base repetition does not remove the Carmichael-number limitation.

Confusing the Fermat test with Fermat numbers

They are different ideas. Fermat numbers have the form 2^{2^m} + 1. The Fermat primality test is based on Fermat's little theorem and applies to general integer candidates.

What a Fermat Result Really Tells You

Fail: the candidate is composite. The chosen base is a Fermat witness.

Pass: the candidate behaves like a prime for that base, but it may still be composite.

Repeated pass: confidence may improve for ordinary composites, yet the basic Fermat test still cannot rule out Carmichael numbers.

The test is therefore strongest as a compositeness detector. A witness gives a definite answer. A pass gives a reason to keep testing.

Fermat Primality Test: Method and Limitations