Exercise 1.27 of SICP

Exercise 1.27: Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether an is congruent to a modulo n for every a

Carmichael Numbers: 561: 3 11 17 1105: 5 13 17 1729: 7 13 19 2465: 5 17 29 2821: 7 13 31 6601: 7 23 41 > (test-prime? 561) #t
> (test-prime? 1105)
#t
> (test-prime? 1729)
#t
> (test-prime? 2465)
#t
> (test-prime? 2821)
#t
> (test-prime? 6601)
#t

These number indeed fool the test. I will trace through a case where a=10 and n=561. I will leave the remainder procedure out to save text space but I will apply it as if it is there. I don’t think much is left out by applying remainder implicitly.

This exercise and the Miller-Rabin test are getting me to think about Discrete Logarithms.

Leave a Reply