問題1-27

Carmichael数がフェルマーテストをクリアしてしまうことをかくにんします。
フェルマーテストは整数に関して、[tex:a

(use srfi-19)

(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 (carmichael-test n)
  (define (sub-carmichael-test n a)
    (cond ((= a 0) #t)
	  ((= (expmod a n n) a) (sub-carmichael-test n (- a 1)))
	  (else #f)))
  (sub-carmichael-test n (- n 1)))

1729はCarmichael数ですが、

gosh> (carmichael-test 1729)
#t

こんな感じで、フェルマーテストをクリアしてしまう。