How is the modulo affected by exponentiation?

Question

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?

Answer 1

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

Answer 2

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