SICP: Exercise 1.27

問題 1.27

脚注 47 の Carmichael 数が本当に Fermat テストをだますことを示せ。それには整数 \( n \) をとり、\( a < n \) なるすべての \( a \) で、\( a^n \) が \( n \) を法として \( a \) の合同になるかどうか見る手続きを書き、Carmichael 数でその手続きを使ってみる。

「計算機プログラムの構造と解釈 第二版 1.2.6 例：素数性のテスト」より

脚注 47 で挙げられている Carmichael 数は 561, 1105, 1729, 2465, 2821 および 6601。問題文に従ってテストする。

Fermat テストをだます数（Fermat の小定理より素数もそのような数になる）かどうかを調べる手続きは

(define (fool-fermat-test? n)
  (define (iter a)
    (cond ((= a 0) #t)
          ((= (expmod a n n) a) (iter (- a 1)))
          (else #f)))
  (iter (- n 1)))

それではまとめて調べてしまおう。

(define carmichael-numbers '(561 1105 1729 2465 2821 6601))
(map fool-fermat-test? carmichael-numbers)
; (#t #t #t #t #t #t)

確かに脚注 47 の Carmichael 数はすべて Fermat テストをだますようだ。