*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.