Lehmann test is a primality test – it determines whether the given integer is composite or a prime.

## Description

Little Fermat's theorem states that for every prime it holds that

Hence it also holds

If we use the formula to expand the expression, we get

From divisibility of numbers, we know

So, if the equation holds, than one of the following conditions must also hold

Finally, provided that

than may be a prime. In any other case is a composite number, because it contradicts the *Little Fermat's theorem*. It can be shown that every iteration of Lehmann test eliminates at least fifty percent of composite numbers.

Probability that the number is a prime after iterations of Lehmann test can be expressed as