SICP Exercise 1.27

sicp

Question

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^n\) is congruent to \(a\) modulo \(n\) for every \(a\lt n\), and try your procedure on the given Carmichael numbers.

Answer

Here is my code. I added a few intentionally wrong numbers at the end to test for false positives.

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

(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 (try-it a n)
  (cond ((= a (expmod a n n)) true)
        (else false)))

(define (carmichael? n)
  (define (try-carmichael n counter)
    (cond ((= counter 0) true)
          ((try-it counter n) (try-carmichael n (- counter 1)))
          (else false)))
  (try-carmichael n (- n 1)))

(display "These should be true:") (newline)
(carmichael? 561)
(carmichael? 1105)
(carmichael? 1729)
(carmichael? 2465)
(carmichael? 2821)
(carmichael? 6601)

(display "These should be false:") (newline)
(carmichael? 100)
(carmichael? 34)
(carmichael? 2001)
(carmichael? 777)

And the results:

These should be true:
#t
#t
#t
#t
#t
#t
These should be false:
#f
#f
#f
#f