(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 (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (define (fermat-test-iter n aval)
    (cond ((= aval 0) #t)
          ((try-it aval) (fermat-test-iter n (- aval 1)))
          (else #f)))
  (fermat-test-iter n (- n 1)))

수행결과

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

561 은 알다시피 3 의 배수로 소수가 아니다. 다른 수들도 모두 마찬가지로 소수가 아닌데, fermat test 를 통과한다. fermat test 를 만든 페르마도 대단하지만 위 수들을 찾은 양반들도 대단하다. 정수론은 수학에서도 아주 독특한 분야인 것 같다.