SICP Exercise 1.27: Carmichael Numbers

Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether aⁿ is congruent to a modulo n for every a<n, and try your procedure on the given Carmichael numbers.

Footnote 47 states that:

"Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a "correct" algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

So we want to check that the following numbers fool the Fermat test: 561, 1105, 1729, 2465, 2821, and 6601.

Before we do that, we need a procedure that performs the Fermat test for all values in the range 1≤a<n. First, let's look at the original fermat-test implementation:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

This has an internal procedure definition for try-it, which tests whether or not the Fermat test holds for a single integer, a, which fermat-test calls using a random value in the range 1≤a<n. We can use this as the basis for a new procedure (which I've called it fermat-test-all) by removing the randomness and replacing it with iterative testing of all of the values in the range 1≤a<n. To do this we:

• Modify try-it that:
  1. It checks to see if the Fermat test holds for the current value of a.
  2. If it does then it calls itself for the next value of a.
  3. If it doesn't then it returns #f.
  4. If it reaches a=n then it returns #t, as the Fermat test has succeeded for all tested numbers.
• Modify the outer call to try-it so that it starts at 1.

Here's the updated procedure:

(define (fermat-test-all n)
  (define (try-it a)
    (cond ((= a n) #t)
          ((= (expmod a n n) a) (try-it (+ a 1)))
          (else #f)))
  (try-it 1))

I also produced a procedure charmichael? that checks whether or not a given number is a Charmichael number or not. I.e. it checks to see that it passes the Fermat test and it checks that the number is not prime:

(define (charmichael? n)
  (and (fermat-test-all n) (not (prime? n))))

When we run this for the given Charmichael numbers we get:

> (charmichael? 561)
#t
> (charmichael? 1105)
#t
> (charmichael? 1729)
#t
> (charmichael? 2465)
#t
> (charmichael? 2821)
#t
> (charmichael? 6601)
#t

...and just as a quick sanity check:

> (charmichael? 1)
#f
> (charmichael? 2)
#f
> (charmichael? 3)
#f
> (charmichael? 4)
#f
> (charmichael? 5)
#f
> (charmichael? 6)
#f
> (charmichael? 7)
#f