Programming Praxis

Pierre de Fermat’s little theorem states that if p is prime, then for any integer a, a^p − a is evenly divisible by p, which is usually stated as a^p ≡ a (mod p); Fermat’s little theorem is often stated as the corollary a^p−1 ≡ 1 (mod p).

By turning it around, Fermat’s little theorem may be used as a primality test: if you can find an a for which a^p−1 ≢ 1 (mod p), then p is certainly composite; for instance, 2⁶² ≡ 4 (mod 63), so 63 is composite, and 2 is a witness to its compositeness. Thus Fermat’s primality test consists of choosing many numbers and checking if they are witnesses to the compositeness of the number being tested.

Unfortunately, there are some composite numbers which pass Fermat’s primality test for all possible witnesses; they are called Carmichael numbers, after Robert Carmichael, who studied them. Carmichael discovered in 1910 that 561 is a Fermat pseudo-prime to all possible bases.

One way to test that a number is a Carmichael number is to test all primes less than the number that are coprime to it. A faster test, due to Alwin Korselt, notes that Carmichael numbers are odd, composite, square-free (no factors appear more than once) and f−1 ∣ n−1 for all factors f of n.

Because there exist numbers that fool Fermat’s primality test for all bases, a strong pseudo-primality test is often used. A composite number n = d · 2^s + 1 with d odd is a strong pseudoprime to a relatively prime base a if and only if either a^d ≡ 1 (mod n) or a^d·2r ≡ −1 (mod n) for some 0 ≤ r ≤ s−1. For instance, 2³¹ ≡ 2 (mod 63), so 63 = 31 · 2¹ + 1 is composite, and 2 is a witness to that compositeness. The beauty of the strong pseudo-primality test is that it harbors no “Carmichael numbers;” every composite has at least one strong witness.

Your tasks are to write two functions that test if a number is a Fermat pseudo-prime or a strong pseudo-prime to a given base, two functions that test primality using the Fermat and strong pseudo-prime tests, and two functions that test if a number is a Carmichael number, and to identify all the Carmichael numbers less than 10,000. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2