# Fermatscher primality test

The Fermat's prime test is a prime test based on Fermat's small theorem . It is used to distinguish prime numbers from composite numbers .

## Fermatscher primality test

The Fermat's prime number test is based on Fermat's small theorem:
For every prime number and every coprime natural number , the following congruence is fulfilled: ${\ displaystyle p}$${\ displaystyle a}$

${\ displaystyle a ^ {p-1} \ equiv 1 \ mod p}$ .

By reversing this condition, one can test for natural numbers whether they are composed. If for a basis that is too coprime it is not divisible by, then it can not be prime. For example, one can conclude that the number is a compound. ${\ displaystyle a ^ {n-1} -1}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle 2 ^ {8} = 256 = 28 \ cdot 9 + 4 \ equiv 4 \ mod 9}$${\ displaystyle n = 9}$

The Fermatsche primality test goes like this:

• Input :, the natural number to be tested, result: composite or no statement${\ displaystyle n}$
• Choose a base with . Check whether and are coprime.${\ displaystyle a}$${\ displaystyle 1 ${\ displaystyle n}$${\ displaystyle a}$
If they are not coprime then the result is composite . Otherwise:
If so, the result is a composite .${\ displaystyle a ^ {n-1} \ not \ equiv 1 \ mod n}$
Otherwise the result is not a statement

If the test is repeated several times with different bases, no statement can be interpreted as a presumably prime number .

## Fermatsche pseudoprimes

However, there are natural numbers that are not prime numbers and for which it still holds for a relatively prime basis that is divisible by . Such numbers are called Fermatian pseudoprimes for the base . The Carmichael numbers are particularly stubborn Fermatian pseudoprimes . For this is for all to prime bases by divisible. ${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle a ^ {n-1} -1}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle a ^ {n-1} -1}$${\ displaystyle n}$${\ displaystyle n}$

If you use Fermat's prime number test with the base , you can determine with a high degree of certainty whether a number is a prime number or not. The following table shows the result of the calculation for the numbers 3 to 29. ${\ displaystyle a = 2}$

 ${\ displaystyle n}$ 3 4th 5 6th 7th 8th 9 10 11 12 13 14th 15th 16 17th 18th 19th 20th 21st 22nd 23 24 25th 26th 27 28 29 ${\ displaystyle 2 ^ {n-1} {\ bmod {n}}}$ 1 0 1 2 1 0 4th 2 1 8th 1 2 4th 0 1 14th 1 8th 4th 2 1 8th 16 2 13 8th 1

This table can to be continued and is always under each prime number is a 1 and below each composite number is a number other than 1. The 341 is namely the first Fermat pseudoprime respect to the base 2: 341 is a divisor of , but due not prime. ${\ displaystyle n = 340}$${\ displaystyle 2 ^ {340} -1}$${\ displaystyle 341 = 11 \ cdot 31}$

Until there are 303 prime numbers, but only 7 Fermatian pseudoprimes with respect to 2, namely 341, 561, 645, 1105, 1387, 1729 and 1905 (sequence A001567 in OEIS ). If you choose a different basis, you get similar results. It was proved by Paul Erdős that the pseudoprimes are infinitesimally few on each base compared to the prime numbers (for each base , the number of Fermat's pseudoprimes is smaller than divided by the number of prime numbers smaller than converges with increasing to zero). ${\ displaystyle n = 2000}$${\ displaystyle a}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle x}$

## Deterministic Uses and Alternatives

If you use base 2, then you are sure to get a correct result up to the number 340. If you test with several bases (for example 2, 3 and 5), the safe limit increases. For example, the test with bases 2 and 3 is correct up to 1104; when using bases 2, 3 and 5 the limit increases to 1728.

In practice other primality tests are preferred, e.g. B. the Miller-Selfridge-Rabin test , as they are more likely to rule out the case that a composite number is not recognized as such.

However, there were further developments of the Fermat primality tests: for example, introduced in 1983, the mathematician Leonard M. A dleman , Carl P omerance , Robert R umely , H. C heights and Hendrik W. L coastal road Jr. named after them APRCL test before .