SICP Exercise 1.27: Carmichael numbers

From SICP section 1.2.6 Example: Testing for Primality

Exercise 1.27 asks us to demonstrate that the first six Carmicheal numbers (561, 1105, 1729, 2465, 2821, and 6601) really do fool the Fermat test. We're to write a procedure that takes an integer n and tests whether aⁿ is congruent to a modulo n for every value less than n, then test the procedure on each of the Carmichael numbers listed.

The fermat-test procedure that we first saw in exercise 1.24 is a good starting point.

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

Let' start by modifying this procedure so that we pass it the value to test, instead of generating a random value.

(define (fermat-test n a)
   (= (expmod a n n) a))

Now we just need to define a new procedure that will call this one for every value less than the one we want to test. If fermat-test passes for all values tested we should return true, but if it fails for any value we should return false. Here is the complete code listing for the exercise.

(define (square x)
   (* x x))

(define (even? n)
   (= (remainder n 2) 0))

(define (expmod base exp m)
   (cond ((= exp 0) 1)
         ((even? exp)
          (remainder (square (expmod base (/ exp 2) m))
                      m))
        (else
          (remainder (* base (expmod base (- exp 1) m))
                     m))))

(define (fermat-test n a)
   (= (expmod a n n) a))

(define (fermat-full n)
   (define (iter a)
     (cond ((= a 1) #t)
           ((not (fermat-test n a)) #f)
           (else (iter (- a 1)))))
   (iter (- n 1)))

Prime numbers will legitimately pass this test, and Carmichael numbers will fool it. All other composites should fail. You can test out a few primes and composites in a Scheme interpreter to make sure it works as described. Here's the output for the first six Carmichael numbers.

> (fermat-full 561)
#t
> (fermat-full 1105)
#t
> (fermat-full 1729)
#t
> (fermat-full 2465)
#t
> (fermat-full 2821)
#t
> (fermat-full 6601)
#t

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.