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:
- Pick a random element
from the congruence classes of nonzero integers mod 
(exclude the congruence class of 0). Explicitly, pick as an integer among 
.
- 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.
