Modular exponentiation is essentially a technique used to calculate \( c = b^e \: mod \: m \) mostly used in computer programming. Let's say you want to calculate \( 97^{59} \: mod \: 8 \). \( 97^{59} \) is far too big a value to be calculated and housed in the typical variable. And that's why we need this "special technique".

The heart of the idea in equation form writes out as \( (ab) \: mod \: m = a(b \: mod \: m) \). All the modular divisions might make it look so complicated. But, no, the idea is very simple and intuitive. Let's say we want to find the least significant digit of \( 7^9 \). When multiplying 7 nine times, instead of retaining the entire result, we discard everything except the least significant digit.

So, it goes like

• \( 7 \times 7 = 49 \equiv 9 \)
• \( 9 \times 7 = 63 \equiv 3 \)
• \( 3 \times 7 = 21 \equiv 1 \)
• \( 1 \times 7 = 7 \equiv 7 \)
• \( 7 \times 7 = 49 \equiv 9 \)
• \( 9 \times 7 = 63 \equiv 3 \)
• \( 3 \times 7 = 21 \equiv 1 \)
• \( 1 \times 7 = 7 \equiv 7 \)

And yes, true enough \( 7^9 = 40,353,607 \). The last digit is indeed 7.

Now, that was simple. Essentially, what we did just now was \( 7^9 \: mod \: 10 \). Retaining the least significant digit at each step is the same as modular division with 10. Now, this technique can be easily generalized from mod 10 to any mod m. Also, in order to better visualize this, it might be convenient to think of mod m as retaining the least significant digit in a number system of base m.

So, let us take a look at another example. Say, we need to calculate \( 26^{11} \: mod \: 7 \). 26 expressed in a base 7 number system would be 35.

• \( 5 \times 5 = 34 \equiv 4 \)
• \( 4 \times 5 = 26 \equiv 6 \)
• \( 6 \times 5 = 42 \equiv 2 \)
• \( 2 \times 5 = 13 \equiv 3 \)
• \( 3 \times 5 = 21 \equiv 1 \)
• \( 1 \times 5 = 5 \equiv 5 \)
• \( 5 \times 5 = 34 \equiv 4 \)
• \( 4 \times 5 = 26 \equiv 6 \)
• \( 6 \times 5 = 42 \equiv 2 \)
• \( 2 \times 5 = 13 \equiv 3 \)

Verifying results,

\[ 26^{11} = 3,670,344,486,987,776 \] \[ 26^{11} \: mod \: 7 = 3 \]