Fermat Primality Test

Number Theory · Axiom Academy

Using Fermat's Little Theorem to efficiently test whether a number is (probably) prime The foundation of the Fermat Primality Test is Fermat's Little Theorem, one of the most important results in elementary number theory. This means that when we raise a to the power p-1 and divide by p , we always get a remainder of 1. This property is true for all primes. The Fermat test turns the theorem around: if n is prime, then the congruence must hold. So if we find that it doesn't hold, then n must be composite. When the test finds that a n-1 ≢ 1 (mod n), we've found a Fermat witness to the compositeness of n . This gives us absolute certainty that n is composite. However, if the test passes (a n-1 ≡ 1), we can only say n is probably prime, because some composite numbers can pass the test for certain values of a . 3. Increasing Confidence Through Repetition Since a single Fermat test is probabilistic, we increase our confidence by running the test multiple times with different random values of a . For most composite numbers, at least half of the possible bases will reveal their compositeness. This means: After k random tests, the probability that a composite number passes all tests is at most (1/2) k After 10 tests: probability ≤ 1/1024 ≈ 0.1% After 20 tests: probability ≤ 1/1,048,576 ≈ 0.0001% 4. The Limitation: Carmichael Numbers Unfortunately, there exist rare composite numbers called Carmichael numbers that pass the Fermat test for all bases a coprime to n .

This is the written version of the interactive lesson above. See the full Number Theory course.