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

| improve this answer | |

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

| improve this answer | |
  • $\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


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

| improve this answer | |

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.