Exercise 1.27

Imports: [[Chapter 1.2]] prime? expmod

(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-all? n) 
  (define (iter a) 
    (or (>= a n) 
        (and (= (expmod a n n) a) 
             (iter (+ a 1))))) 
   (iter 1))

These Carmichael numbers pass the Fermat tests for all values \(a < n\):

(fermat-all? 561) => #t
(fermat-all? 1105) => #t
(fermat-all? 1729) => #t
(fermat-all? 2465) => #t
(fermat-all? 2821) => #t
(fermat-all? 6601) => #t

According to the trial division procedure, none of them are prime:

(prime? 561) => #f
(prime? 1105) => #f
(prime? 1729) => #f
(prime? 2465) => #f
(prime? 2821) => #f
(prime? 6601) => #f