# Fermat primality test

## Definition

The Fermat primality test is a quick and often inconclusive primality test. In the version below, we consider only .

Given a natural number , the test works as follows:

1. Pick a random element  from the congruence classes of nonzero integers mod  (exclude the congruence class of 0). Explicitly, pick  as an integer among .
2. Check whether . To compute the power use repeated squaring. If the condition does not hold, then  is composite. If the condition does hold, then  may be prime or composite.

The above is a single iteration of the test. Multiple iterations of the test may be carried out with multiple random elements. If at any stage the condition  is violated, we can conclude that the number is composite. If, however, the condition holds every time, the situation is inconclusive and  may be prime or composite.

## Theory

### Why it works

The primality test above is correct because of Fermat's little theorem, which says that for a prime  and  relatively prime to , we have:



### Behavior on composite numbers

For any composite number , we use the following terms:

• A Fermat witness for  is a value  such that .
• A Fermat liar for  is a value  such that .
• We say that  is a Fermat pseudoprime to base  if  is a Fermat liar for .

Nonzero numbers that have a common factor with  always serve as Fermat witnesses. There are  of these where  is the Euler totient function. For  composite, this number is at least equal to , the worst case arising when  is a square of a prime. In general, if  has a small number of large prime factors, there are very few such numbers and a uniform random choice is highly unlikely to hit them.

For the numbers that are relatively prime to , we have the formula for probability of relatively prime integer being a Fermat liar. If the probability is 1, then  is a Carmichael number. If the probability is less than 1, then it is at most 1/2, which means that the Fermat primality test can find a witness with arbitrarily high probability of success in a finite number of trials.