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

-
How g^b mod p = g^b + pK? – codeomnitrix Jul 25 '14 at 9:42
@codeomnitrix, $a \equiv b\pmod c$ is a shorthand notation for $\exists k : a - b = ck$ – Peter Taylor Jul 30 '14 at 9:34
Thanks Peter... – codeomnitrix Jul 30 '14 at 15:35
are u sure about (g^b mod p)^a ≡ g^(ab) mod p? lets try with g = 2, a = 1, b = 3, p== 11 (2^3 mod 11) ^ 5 != 2 ^ (5*3) mod 11 as obviously 8^5 != 2^15 mod 11 – Dmitry Martovoi Jun 30 at 11:27
@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 Jun 30 at 11:33