# Proof for exponentiation in modular arithemtic

If $e$ is a natural number, then this is true:

$$m^e \bmod\ n = (m\bmod\ n)^e\bmod\ n$$

This is often used when encrypting, especially with RSA, since one can avoid directly calculating $m^e$, which can be a very big number.

However, I haven't been able to find any documentation/proof for this conjecture, can anyone give a source or explain it?

• For every possible integer calculation the following holds: If an euqation is true in $\mathbb{Z}$, then it is also true in every $\mathbb{Z}/n\mathbb{Z}, n \in \mathbb{N}$. – tylo Feb 3 '14 at 14:38
• @tylo: unless the calculation/equation involves division. E.g. $\displaystyle\frac 22=1$ holds in $\mathbb{Z}$, but is undefined/does not hold in $\mathbb{Z}/2\mathbb{Z}$. – fgrieu May 5 at 17:07

That is not a conjecture, that is basic number theory and follows from the fact that

$$(ab)\textrm{ mod } n = \big((a\textrm{ mod } n)\cdot(b\textrm{ mod } n)\big)\textrm{ mod } n$$

Write $$a=k_an+r_a$$ and $$b=k_bn+r_b$$ and thus $$a \textrm{ mod } n = r_a$$ and $$b \textrm{ mod } n = r_b$$. Plugging into the left hand side will give you:

\begin{align}\big((k_an+r_a)(k_bn+r_b)\big)\textrm{ mod } n &= \big((k_a k_b n + k_a r_b+ k_br_a )n + (r_a r_b)\big)\textrm{ mod } n \\ &= (r_a r_b)\textrm{ mod } n\end{align}

The last step is because any multiple of $$n$$ clearly yields a zero remainder when divided by $$n$$.

Plug into the right hand side gives you $$(r_a r_b ) \textrm{ mod } n$$. This shows the equality which is what you're looking for.

Viewing the exponentiation $$m^e \textrm{ mod } n$$ as $$(m \cdot \ldots \cdot m) \mod n$$ (multiplying $$m$$ with itself $$e-1$$ times), then you have what you are looking for.

You can arrive at a simple proof by induction, using the more basic theorem that:

$$a \times b \bmod n = (a \bmod n) \times (b \bmod n) \bmod n$$

With that, then the inductive proof goes as:

• It is true for $e = 1$. This can be seen as:

$$m^1 \bmod n = (m \bmod n)^1 \bmod n$$

• If it is true from $e = k-1$, then it is true for $e = k$. This is, if we posit that:

$$m^{k-1} \bmod n = (m \bmod n)^{k-1} \bmod n$$

then, if we multiply both sides by $m \bmod n$, we get:

$$m^{k-1} \times m \bmod n = (((m \bmod n)^{k-1} \bmod n)\times m \bmod n$$

or (using the basic theorem on the right side):

$$m^{k} \bmod n = (m \bmod n)^{k-1} \times (m \bmod n) \bmod n$$

or

$$m^{k} \bmod n = (m \bmod n)^{k} \bmod n$$

• How do you know it is true for $e = k-1$? – Gretty Feb 2 '14 at 18:56
• This is a proof by induction. We know it is true for $e = 1$. Using the formula in the answer, we can then prove it is true for $e = 2$ as well, and then for $e = 3$ etc. No matter how large $e$ gets, we might prove that the formula is true for $e + 1$ as well. Hence, by induction, it is true for all integer values of $e$. – Henrick Hellström Feb 2 '14 at 20:50

Write

$$m = pn+r \Rightarrow \ m \bmod \ n =r \Rightarrow r^e = (m \bmod \ n)^e \quad (1)$$

Using the Binomial Theorem,

\begin{align} \ m^e = (pn+r)^e & = [(pn)^e+e\cdot(pn)^{e-1} \cdot r+\cdots+ e \cdot (pn) \cdot r^{e-1} + r^e] \\ & = [(pn)^{e-1}+e\cdot(pn)^{e-2} \cdot r+\cdots+ e \cdot r^{e-1}] \cdot (pn) + r^e \\ &= d \cdot n + r^e \end{align}

where $$\ d = [(pn)^{e-1}+e\cdot(pn)^{e-2} \cdot r+ \cdots + e \cdot r^{e-1}] \cdot p$$

So, $$\ m ^e \bmod \ n = ( d \cdot n + r^e ) \bmod \ n = r^e \bmod \ n \$$

Using $$\ (1)$$,

$$\ m ^e \bmod \ n = (m \bmod \ n)^e \bmod \ n$$