Fermat's primality test is a test, prich determines, whether the given integer is a prime or not. It is based on Fermat's little theorem, which states that for every prime and its coprime it holds that:

If the equality does not hold, then we can be sure that the number is not a prime. If it does hold, the number might be a prime.

Example

Testing: 15
We choose: a = 5

We suppose:


The test:

Number is a witness that is not a prime.

Example 2

Testing: 15
We choose: a = 4

We suppose:


The test:

Number implies that is a prime, however it is not (we have determined that it is composite by the previous test). Let's denote number as Fermat liar.

The flaw

The main flaw of the Fermat's primality test is existence of Carmichael numbers. The Carmichael numbers are absolute Fermat's pseudoprimes, which means that they will always pass this test as primes (regardless which base we choose). This implies that there is no way to compute the probability that the number is (not) a prime, provided it has passed through iterations of the test.

For this reason Fermat's test is not often used in favor to other primality tests – for example Rabin-Miller, Solovay-Strassen or Lehmann test.