If a and p are relatively prime, then a has a multiplicative inverse, mod p, and

this can then be rewritten as a raised to the p- 1 power is congruent to 1 (mod p).

This should look familiar since it is a special case of Euler's Totient Theorem.

So how do we construct a primality test from this?

After choosing a random candidate for p, we pick a value for a that is less than 8.

We can't chose 0 since 0 is not relatively prime to any number, including p.

We could choose 1, but this trivially satisfies the relation and so

tells us nothing.

Similarly, since p is going to be an odd number,

since two is the only even prime and two would be a rather poor choice for

a cryptographically useful prime number, then p- 1 will be even.

And hence choosing a = -1, which is congruent to p- 1 (mod p),

will also truly satisfy the relation.

So we pick a value for a such that it lies strictly between 1 and p- 1.

We evaluate a raised to the p- 1 and see if the result is congruent to 1.

If is not, then we have established that p is a composite number and

the value a is known as a Fermat witness to that fact.

But if the result is congruent to 1, then we have two possibilities.

Either p really is prime which is what we're hoping for, or p is actually

composite and this particular choice of a for the base failed to detect it.

When this happens, p is known as a Fermat pseudoprime to the base a,

or just a pseudoprime to the base a, and

the value a is known as a Fermat liar for this value of p.

For a concrete example, let's say that we randomly pick p = 15.

And for the moment, let's assume that this value is too large for

us to even attempt to factor, but we want to see if it is prime.

So we randomly choose a value of a that's equal to 4 and

calculate 4 to the 14 (mod 15) = 1.

We discover that it is indeed congruent to 1, so 15 might be prime.

But since we know that it might not be, we hedge our bets and

pick another value of a and choose 2.

2 to the 14th power (mod 15) is congruent to 4.

So this proves that 15 is composite and 2 is a Fermat witness for 15.

But since it passed the test for a for a base of 4,

we call 15 a Fermat pseudoprime to the base 4 and 4 is a Fermat liar for 15.

In general, the more bases we choose to test,

the more likely we are to find a Fermat witness should p not be prime.

But this isn't guaranteed, and in fact, It's actually possible to find a number

that is pseudoprime for every possible choice of a.

For these numbers, we could exhaustively test every possible base and

conclude that the number almost has to be prime.

These numbers are called Carmichael numbers and

the smallest such number is 561.

While there are infinitely many Carmichael numbers,

they're actually pretty rare in comparison to the non-Carmichael pseudoprimes.

Hence the odds are well in our favor that if we test a number against

a lot of bases and we do not find a Fermat witness, that the number is prime.

Because the Fermat test is simple,

it is often done as the first in a suite of tests.

The idea to quickly rule out most selections as being not prime and

then carrying out better, and usually slower, tests on the survivors

to further increase the confidence in the primality of the number.

But this isn't always the case and there are some mainstream cryptographic

protocols that rely on Fermat's primality test alone to choose prime numbers.