#lang racket  ; needed for true / false

(define (square n)
  (* n n))

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

(define (is-carmichael-prime? n)
        (fermat-test n (- n 1)))

561
(is-carmichael-prime? 561)
1105
(is-carmichael-prime? 1105)
1729
(is-carmichael-prime? 1729)
2465
(is-carmichael-prime? 2465)
2821
(is-carmichael-prime? 2821)
6601
(is-carmichael-prime? 6601)