# 1.27

## 练习 1.27： 证明脚注47中列出的Carmichael数确实能骗过费马检查。也就是说，写一个过程，它以整数n为参数，对每个a < n检查an是否与a模n同余。用你的过程去检查前面给出的那些Carmichael数。

(define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (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 (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) m) ) (else (remainder (* base (expmod base (- exp 1) m)) m) ) ) ) (define (test-carmichale n) (start-carmichale-test n 1)) (define (start-carmichale-test n start) (display start) (display "^") (display n) (display " mod ") (display n) (display "=") (display (expmod start n n)) (display " === ") (display start) (display " *** ") (display start) (display "^2 = ") (display (* start start)) (display " mod ") (display n) (display " = ") (display (remainder (* start start) n)) (newline) (if (< start (- n 1)) (start-carmichale-test n (+ start 1)) (display "测试结束！") ) ) (newline) (display "检查 561 是否为 Carmichale 数 ：") (newline) (test-carmichale 561) (newline) (display "检查 1105 是否为 Carmichale 数 ：") (newline) (test-carmichale 1105) (newline) (display "检查 1729 是否为 Carmichale 数 ：") (test-carmichale 1729) (newline) (display "检查 2465 是否为 Carmichale 数 ：") (test-carmichale 2465) (newline) (display "检查 2821 是否为 Carmichale 数 ：") (newline) (display "检查 6601 是否为 Carmichale 数 ：") (newline)