# Modular arithmetics in diffie-hellman

Studying the basics of Diffie-Hellman key exchange, I'm stuck at a basic operation used in the end of the key exchange (where you show that both computations actually are the same). Can someone explain this step in detail?

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


Where p is a prime and g is the primitive root to p

Thanks,

• Actually, that holds for arbitrary $g, p$. That is, that's true even if $p$ isn't a prime, and/or $g$ is not a primitive root. – poncho Nov 10 '15 at 18:59

This can be derived from two simple facts about the $mod$ operation:

$a \bmod b = a + bi$ for some integer $i$ (for any $a, b$)

$a \bmod c = b \bmod c$ if $a - b = ci$ for some integer $i$

With these two facts, we can look at $(g^a \bmod p)^b$; that can be simplified to $(g^a + pi)^b$ (for some integer $i$), and by the binomial expansion, this is $g^{ab} + p(\textit{Other terms})$ (for some integer value of Other terms).

When we look at the difference between that and $(g^a)^b$, we get the value $g^{ab} + p(\textit{Other terms}) - (g^a)^b = p(\textit{Other terms})$, which is $p$ times some integer.

Hence, by our second fact, we immediate get $(g^a \bmod p)^b \bmod p = (g^a)^b \bmod p$, which is what we set out to prove

• I think you'd also need "and only if" for the latter of those two facts. $\;$ – user991 Nov 10 '15 at 19:24
• @RickyDemer: actually, we don't need it; the proof would be valid even if there were cases that $a \bmod c = b \bmod c$ even if there was no such $i$. Of course, that doesn't happen; however we don't need to assume it :-) – poncho Nov 10 '15 at 19:27
• (In fact, as I now notice, the "and only if" part follows from the former of those two facts.) $\;$ – user991 Nov 10 '15 at 19:29