Structure and Interpretation of Programs defines Fermat's Little Theorem thus:
If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.
(Two numbers are said to be congruent modulo n if they both have the same remainder when divided by n. The remainder of a when divided by n is also referred to as the remainder of a modulo n, or simply a modulo n.
Based on that description, I write this code:
(define (fermat-test a n)
(congruent? (expt a n) a n))
(define (congruent? x y n)
(= (modulo x n)
(modulo y n)))
Later, SICP says this:
This leads to the following algorithm for testing primality: Given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not a prime.
and gives this code:
(define (fermat-test)
(define (try-it)
(= (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) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
where expmod is "a procedure that computes the exponential of a number modulo another number".
I don't understand the correspondence between this code and the first definition of Fermat's theorem. I understand "a raised to the nth power is congruent to a modulo n" as: a^n modulo n = a modulo n. But SICP's code seems to imply a^n modulo n = a. The condition in the fermat-test procedure does not include a modulo n. Of course, their implementation works, so I must be misunderstanding.
Please note, this is not a confusion about recursive versus iterative processes.
