# Modular exponentiation¶

Suppose you want to calculate $$5^7 \mod 3$$ and you have to work with unsigned 8 bit integers.

The largest integer we can use is 255 ($$= 2^7 + 2^6 + \cdots + 2^1 + 2^0 = 2^8 - 1$$).

$$5^7 = 78125$$, but our calculator will tell us it equals 45, because of overflow.

$$78125 \mod 3 = 2$$, while $$45 \mod 3 = 0$$, so we won’t get the right answer.

But we can break down the problem as follows:

$$5^7 \mod 3 = 5 \cdot (5^6 \mod 3) \mod 3$$

$$5^6 \mod 3 = (5^3 \mod 3)^2 \mod 3$$

$$5^3 \mod 3 = 5 \cdot (5^2 \mod 3 ) \mod 3$$

$$5^2 \mod 3 = (5^1 \mod 3)^2 \mod 3$$

$$5^1 \mod 3 = 5 \cdot (5^0 \mod 3) \mod 3$$

And then solve each subproblem without ever needing to store an integer larger than 255:

$$5^1 \mod 3 = 5 \cdot (5^0 \mod 3) \mod 3 = 2$$

$$5^2 \mod 3 = 2^2 \mod 3 = 1$$

$$5^3 \mod 3 = 5 \cdot 1 \mod 3 = 2$$

$$5^6 \mod 3 = 2^2 \mod 3 = 1$$

$$5^7 \mod 3 = 5 \cdot 1 \mod 3 = 2$$