# Prove equivalence of Diffie-Hellman shared secret

How can I prove that:

$(g^b \bmod{p})^a \bmod{p} = (g^a \bmod{p})^b \bmod{p}$

where p is a prime number, g is a primitive root of p, and a and b are integers.

While I understand that $(g^b)^a = (g^a)^b$ , I cannot figure out how to deal with the mod functions...

-

You can expand $(g^b \bmod p)$ as $g^b + pK$ by the definition of $\text{mod}$.
Then $(g^b + pK)^a = g^{ab} + \binom{a}{1}g^{(a-1)b}pK + \ldots + (pK)^a$
Since all but the first of the terms in the binomial expansion contain a factor of $p$, $(g^b \bmod p)^a \equiv g^{ab} \bmod p$
@codeomnitrix, $a \equiv b\pmod c$ is a shorthand notation for $\exists k : a - b = ck$ – Peter Taylor Jul 30 '14 at 9:34
@DmitryMartovoi, I have no idea where your 5 came from, but yes, I am sure because I am completely convinced by the proof in the answer. I am also completely convinced that "8^5 != 2^15 mod 11" is obviously false: $8^5 = 2^{15}$ so there's no need to even compute the values mod 11. – Peter Taylor yesterday