Pseudoprimes

Number Theory · Axiom Academy

LESSON Pseudoprimes and Carmichael Numbers When Composite Numbers Disguise Themselves as Primes 1. Fermat's Little Theorem and the Fermat Test Fermat's Little Theorem states that if p is prime and a is not divisible by p , then: This gives us a primality test: to test if n is prime, pick a random base a with gcd(a, n) = 1 and check if a n-1 ≡ 1 (mod n). If this fails, n is definitely composite. If it holds, n is probably prime. A Fermat pseudoprime to base a is a composite number n such that: In other words, n passes the Fermat test for base a even though it's composite. For example, 341 = 11 × 31 is a pseudoprime to base 2: A Carmichael number is a composite number n that is a Fermat pseudoprime to every base a with gcd(a, n) = 1. The smallest Carmichael number is: For 561, we have a 560 ≡ 1 (mod 561) for every a coprime to 561. These numbers completely defeat the basic Fermat test. A composite number n is a Carmichael number if and only if: Let's verify this for 561 = 3 × 11 × 17:

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