(x % mod) ** 2 = x**2 % mod

Question

I read such a algorithms to implement expmod computation in sicp

#+begin_src ipython :session sicp :results output
def expmod(base, exp, m):
    # base case
    if exp == 0: return 1
    if evenp(exp):
        return expmod(base, exp/2, m) ** 2 % m
    else:
        return base * expmod(base, exp-1, m) % m

def evenp(n):
    return n % 2 == 0

print(expmod(2, 8, 7))
 #+end_src

 #+RESULTS:
 : 4

The algorithms employed the principle that

 (x % mod) ** 2 = x**2 % mod

How could prove it?

Answer 1

In general, this is wrong.

E.g.

$$(8\bmod 5)^2=9$$

but

$$(8^2)\bmod5=4.$$