Fermat's primality test

The basis for this test is Fermat's little theorem: For every p\in \mathbb{P} and a\in\mathbb{N} being co-prime to p: a^{p-1} \mod p=1

So to test if a number is x is not a prime number we just take a random number a \in \mathbb{Z}_{p}^{*} where the gcd is 1 and check if a^{x-1} \mod x \neq 1, if that's the case x is not a prime number.

a is also referred to as fermat witness.

Fermat Liar

At this point you can definitely proof that a n is a composite number, but the converse isn't always true. This is partially due to so called Carmichael Numbers; n is a Carmichael number if and only if n is square-free (not divisible by any perfect square other than 1) and for every prime divisor p of n, the quantity (p - 1) divides (n - 1). To check 561 = 3 × 11 × 17: (3-1) = 2 divides 560, (11-1) = 10 divides 560, and (17-1) = 16 divides 560.

If a^{n-1} \mod n = 1 even though n is a composite number, a is referred to as a fermat liar. Not every fermat liars are carmichael numbers, but most of them are.

Related Notes:

• Miller Rabin Test