This is the definition of fast-exp from 1.2.4 that is refered to:

```
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
```

If we rename things to closer match expmod it looks like this:

```
(define (expt base exp)
(cond ((= exp 0) 1)
((even? exp)
(square (expt base (/ exp 2))))
(else
(* base (expt base (- exp 1))))))
```

To get a naive `expmod`

we can, for now, just calculate the remainder of each clause:

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expt base (/ exp 2))) m))
(else
(remainder (* base (expt base (- exp 1))) m))
```

So far we have not used the footnote `(ab) mod m = ((a mod m)(b mod m) mod m)`

. Of course a special case of this is `(aa) mod m = ((a mod m)(a mod m) mod m)`

which gives `(remainder (square a) m) = (remainder (sqaure (remainder a m)) m)`

. We can use this with the `even`

clause so that

```
(remainder (square (expt base (/ exp 2))) m)
```

becomes:

```
(remainder (square (remainder (expt base (/ exp 2)) m))
m)
```

In the middle of this we have the remainder of an exponent so this is equivalent to:

```
(remainder (square (expmod base (/ exp 2) m)) m)
```

Using the new `even`

clause we have

```
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expt base (- exp 1))) m))
```

To simplify the odd clause lets use `E`

in place of `(expt base (- exp 1))`

for now.

By using the defining properties of `mod`

we can say for any number `a`

:

```
a = (+ (* (quotient a m) m) (remainder a m))
```

So it’s also true that:

```
E = (+ (* (quotient E m) m) (remainder E m))
```

substituting this into our `odd`

clause:

```
(remainder (* base E) m)
```

gives:

```
(remainder (* base (+ (* (quotient E m) m) (remainder E m))) m)
```

We can ignore `(* (quotient E m) m)`

because any term containg this is divisible by `m`

and so will evaluate to `0`

when doing the outer `remainder`

, so this equivalent to:

```
(remainder (* base (remainder E m)) m)
```

expanding E to it’s orignal value:

```
(remainder (* base (remainder (expt base (- exp 1)) m)) m)
```

once again, in the middle, we have the remainder of an exponent so this becomes:

```
(remainder (* base (expmod base (- exp 1) m)) m)
```

And our `expmod`

is now:

```
(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))))
```

CLICK HERE to find out more related problems solutions.