# How is the modulo affected by exponentiation?

I was reading on how Diffie-Helman works and the wikipedia article has the following:

$(g^a\;\mathrm{mod}\;p)^b\pmod p \equiv (g^b\;\mathrm{mod}\;p)^a\pmod p$

And that equation is true because of the $(g^a)^b=g^{ab}$ property. However what about the $\mathrm{mod}\; p$ part? Is it affected by exponentiation? If not what guarantees that at the end of the calculation both sides of the equation will be equal?

• Every identity that is true without modulo is true with it. This has nothing to do with exponentiation. – M. Winter Jun 25 '18 at 9:52
• @M.Winter Someone had edited the question and messed up the equation. Please view the updated one. – Konstantine Jun 25 '18 at 12:38
• It seems you are about the change the meaning of your question after some answers were written. If you are interested in whether $(g^a)^b \;\mathrm{mod}\; p$ and $(g^a\;\mathrm{mod}\; p)^b\;\mathrm{mod}\; p$ give the same result, I recommend leaving your question as it is and asking another separate question. – M. Winter Jun 25 '18 at 12:44
• The original question was with the equation as it is now. Someone edited for formatting reasons and forgot to add the $modp$ inside the exponentiation. – Konstantine Jun 25 '18 at 12:44
• I see. This was unfortunate but not your mistake. I consider deleting or rewriting my answer then. – M. Winter Jun 25 '18 at 12:46

Speaken mathematically, $\mathrm{mod}\; p$ is a ring homomorphism from $\Bbb Z \to \Bbb Z/p\Bbb Z$, i.e. it preserves addition and multiplication. In less math slang, this means

$$\def\cmod{\;\mathrm{mod}\;} \def\lmod{\mathrm{mod}\;} (a+b) \cmod p = (a\cmod p)+(b\cmod p)$$ $$(a\cdot b) \cmod p = (a\cmod p)\cdot (b\cmod p)$$

These are not too hard to check. But especially the second one is important for your case. Because this gives

\begin{align*} (g^a \cmod p)^b = \overbrace{(g^a \cmod p) \cdots (g^a \cmod p)}^{b\text{ times}} = \overbrace{(g^a)\cdots(g^a)}^{b\text{ times}} \cmod p = (g^a)^b \cmod p \end{align*}

Having this in place, we have

$$(g^a \cmod p)^b =(g^a)^b \cmod p = (g^b)^a \cmod p =(g^b \cmod p)^a.$$

The second identitiy holds for the reason I already mentioned in the comments: if some identity holds without $\lmod p$, then also with $\lmod p$. And the same now gives

$$(g^a \cmod p)^b \equiv (g^b \cmod p)^a \pmod p.$$

Denote by $-\,\%\, n\colon \mathbb Z\to \{0,1,\dots,n-1\}$ the operation of taking the remainder when dividing by $n$. You want to show that $$(ab)\,\% \,n = (a\,\%\,n) (b\,\%\,n)\,\%\,n.$$ Once this is shown, you can conclude that $$(g^a)\,\%\, n = (g\,\%\,n)^p\,\%\,n.$$

In a more algebraic manner, you define $\%\,n$ in a different way: Denote by $\mathbb Z/n\mathbb Z$ the set of equivalence classes with respect to the relation $x\sim y$ if and only if $n$ dividides $x-y$. For example in $\mathbb Z/3\mathbb Z$ you have the equivalence class $$[1] = \{ \dots, -8, -5, -2, 1, 4, 7, 10, 13, \dots \}.$$ Now you can define $a\,\%\,n$ to be the unique element in $[a]\cap\{0,1,\dots,n-1\}$. On $\mathbb Z/n\mathbb Z$ you now define addition and multiplication by \begin{align*} [a]+[b] &:= [a+b], \\ [a]\cdot[b] &:= [a\cdot b]. \end{align*} You need to show that these give well-defined operations, that is, the definitions are independent of the choice of representatives: when $a\sim a'$ and $b\sim b'$ you have $[a+b]=[a'+b']$ and $[ab]=[a'b']$.

Multiplication on $\mathbb Z/n\mathbb Z$ being well-defined then implies your statement about products and $\,\%\,n$.

• You didn't read the question carefully. If amounts to the obvious $a=b\implies a\equiv b\mod p$. – Yves Daoust Jun 25 '18 at 10:06