sicp exercise 1.27

;  Exercise 1.27. 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<n, and try your procedure on the given Carmichael numbers.


(define (carmichael index)
   (cond ((= index 1)  561)
         ((= index 2) 1105)
         ((= index 3) 1729)
         ((= index 4) 2465)
         ((= index 5) 2821)
         ((= index 6) 6601)
         (else 0)))

(define (square num) (* num num))

(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 (prime-test n base )
          (if (= (expmod base n n) base)(display "prime\n")))

(define (prime-carmichael-test num)
   (define (prime-carmichael-test-impl base)
      (cond ((= base num) 0)
            (else (prime-test num base) (prime-carmichael-test-impl (+ base 1)))))
   (prime-carmichael-test-impl 2))



(prime-carmichael-test (carmichael 1))(newline)
(prime-carmichael-test (carmichael 2))(newline)
(prime-carmichael-test (carmichael 3))(newline)
(prime-carmichael-test (carmichael 4))(newline)
(prime-carmichael-test (carmichael 5))(newline)
(prime-carmichael-test (carmichael 6))(newline)

; The Carmichael numbers are not prime numbers, but the Fermat test gives a very high probability of
; them being a prime.