It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become extremely large as the exponent increases in value. The following rule provides a great computational advantage when doing modular exponentiation.
The rule for doing exponentiation in modular arithmetic is:
This states that if we take an integer 
, raise it to an integer power 
and calculate the result modulo 
we will get the same result as if we had taken modulo first, raise it to , and calculate that product modulo .
Proof
I’m winging it on this one, but the quotient remainder theorem hasn’t let me down yet, so I am going to start by defining and using it:
where 
this means that 
where 
this means that 
This time we will just substitute for in the left hand side of our exponentiation rule:
The binomial theorem gives us an easy way to expand the binomial we just introduced:
![a^b \bmod{c} = [{b \choose 0}(cq_1)^b + {b \choose 1}(cq_1)^{b-1}r_1^1 + ... + {b \choose {b-1}}(cq_1)^1r_1^{b-1} + {b \choose b}r_1^b] \bmod{c}](https://neuraldump.net/wp-content/ql-cache/quicklatex.com-d65eaccffe6a80c35460804d969323d3_l3.png "Rendered by QuickLaTeX.com")
Fortunately, because we are taking the result modulo c, we can eliminate any terms in the expanded binomial that contain c, leaving us with:
b choose b is equal to 1, so:
From our definition of using quotient remainder theorem, 
:
And that, as they say, is all she wrote.