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

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

$$(a \cdot b)\mod n = ((a \mod n)\cdot(b\mod n))\mod n$$

Write $a=k_a\cdot n+r_a$ and $b=k_b\cdot n+r_b$ and thus $a \mod n = r_a$ and $b \mod n = r_b$ and then plugging into the left hand side will give you:

$((k_a\cdot n+r_a)\cdot (k_b\cdot n+r_b))\mod n = ((k_a\cdot k_b \cdot n + k_a \cdot r_b+ r_a \cdot k_b)\cdot n + (r_a \cdot r_b))\mod n = (r_a \cdot r_b)\mod n$

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 \cdot r_b ) \mod n$ and this shows the equality and that's what you want to have.

Viewing the exponentiation $m^e \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.

-
Thank you very much, now it all makes sense. – Gretty Feb 2 '14 at 20:19

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