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?

  • $\begingroup$ 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}$. $\endgroup$ – 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.


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$$


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

  • $\begingroup$ How do you know it is true for $e = k-1$? $\endgroup$ – Gretty Feb 2 '14 at 18:56
  • $\begingroup$ 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$. $\endgroup$ – Henrick Hellström Feb 2 '14 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.