Why does $(g^b \bmod m)^a \bmod m = (g^a \bmod m)^b \bmod m$?

Question

I have been trying to understand why the Diffie Dellman key exchange algorithm works, specifically why the two exponents can be swapped in it without the result changing.

So my specific question is why:

$$\begin{align} &(g^b \bmod m)^a \bmod m\\ =\ &(g^a \bmod m)^b \bmod m\end{align}\qquad$$

I am interested in the reasoning/proof/explanation behind why it is true.

I am completely aware that it can be proved from common rules of modular arithmetic, but I am asking for a detailed proof/explanation for why it holds true as at least for me the proof isn't immediately obvious.

Answer 1

Generally, to prove an equality about mod as an operation it is usually easiest to convert it into an equivalent but more flexible congruence relation form, via the following equivalence (cf. here)

$$ (g\bmod m) = (h\bmod m)\color{#c00}\iff g\equiv h\!\!\!\pmod {\!m}\qquad $$

$\begin{align} {\rm so}\ \ \ (g^b\bmod m)^a\bmod m &= (g^a \bmod m)^b\bmod m\\[.2em] \color{#c00}\iff (g^b\bmod m)^a &\equiv (g^a \bmod m)^b \!\!\!\pmod{\!m}\\[.2em] \iff (g^b)^a &\equiv (g^a)^b\!\!\! \pmod{\!m}\ \ {\rm by}\ \ \color{#0a0}{\rm CPR}\ \ \color{#c00}{\&}\ \ g^{n}\bmod m\equiv g^n\!\!\!\!\pmod{\!m} \end{align}$

that's true by $\,(g^b)^a = g^{ab} = (g^a)^b\,$ by integer power laws. Here $\color{#0a0}{\rm CPR} = $ Congruence Power Rule

Key Idea $ $ Generally, as above, using the above equivalence and congruence laws, we can erase all $\!\bmod m$ operations in a polynomial expression (i.e. where mod appears in arguments of sums & products, but not in exponents) to obtain an equivalent congruence, e.g. for the above

$$\begin{align}(\color{#c00}{g^b\color{#bbb}{\bmod m})^a\color{#bbb}{\bmod m}} \,&=\, \color{#0a0}{(g^a \color{#bbb}{\bmod m})^b\color{#bbb}{\bmod m}}\\[.2em] \iff \color{#c00}{(g^b)^a} &\equiv\, \color{#0a0}{(g^a)^b}\!\!\pmod{\!m} \end{align}\qquad$$

Since congruence arithmetic inherits all common (ring) arithmetic laws (commutative, associative, distributive), it is much easier to use our well-honed arithmetical (vs. divisibility) intuition to prove congruence equations than it is to prove the equivalent divisibility statements.

Generally, as explained in this answer, in any polynomial expression of integers, i.e, an expression composed of sum and product operations on integers, by inductively applying the congruence sum and product rules we obtain a congruent expression if we replace the arguments of sums and products by congruent integers. Above is a special case: replace all $\,a\bmod m\,$ by $\,a$.

Answer 2

Short answer: all the usual rules of arithmetic are true for calculations modulo $m$.

That means addition and multiplication are commutative and associative and multiplication distributes over addition. The laws of exponents follow.

You have to be a little more careful trying to think about division.

The proofs are standard material in any elementary number theory text.

Answer 3

To answer my own question: The reason why

(g^b mod m)^a mod m

= (g^a mod m)^b mod m

Is because:

(g^b mod m)^a mod m can be simplified to: (g^b)^a mod = g^(ba)

This is because the mod n in the brackets doesn't change the equivalence class of what is being exponentiated to a and multiplying two numbers of the same equivalence class by themselves a certain number of times will result in the same product.

As a result of this, the equation can be represented as g^(ba) mod m = g^(ab) mod m which is obviously true because the product ab is the same either way so the exponent is the same.