Exercise 1.25.  Alyssa P. Hacker complains that we went to a lot of extra work 
in writing expmod. After all, she says, since we already know how to compute 
exponentials, we could have simply written

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime tester? 
Explain. 

------------------------------------------------------------------------

First, a diversion:

The provided expmod relies upon the following equality:

a² % n = (a % n)² % n

An informal proof of which is as follows:

Let b = a - (a % n).

We can see that b%n = 0:

b % n = a%n - (a%n)%n = a%n - a%n = 0

Then,

a = (a % n) + b,

a² = (a%n)² + 2b + b²,

a² % n = ((a%n)² + 2b + b²) % n,

and since b%n = 0,
a² % n = (a % n)² % n          Q.E.D.

It also relies on another equality which I'm not going to prove.

------------------------------------------------------------------------

Given the above, the expmod given in the text computes the same result 
as Alyssa P. Hacker's version, but the results of each squaring are taken 
modulo n at every step.  Since the numbers are much smaller, even though 
the same number of mathematical operations are performed, the interpreter 
can execute the squaring and remainder operations much more quickly.