I've been learning about Diffie-Hellman key exchange.
One of the main tricks comes down to a commutativity property of exponentiation in the relevant modular arithmetic, it seems.
Something like:
(EDIT: As noted by @Ted, I got the formula wrong, hence my confusion.)
$$r^{A^B} \equiv r^{AB} \equiv \; ... \; \equiv r^{B^A} \pmod p$$
I know that this is not true in general, so presumably derives from the particular choices of r, A, B, and p.
I've done a fair amount of searching around, but cannot find a proof, or even a reasonable explanation of where this property arises from.
Can anyone here help?
We have to prove that $$({r^A} \bmod{p})^B \bmod{p} = (r^B \bmod{p})^A \bmod{p} = (r^{AB}) \bmod{p}$$
We would use binomial expansion for it.
Let $r = xp + y$, then $(r) \bmod{p} = y$.
As we know that: $$r^A = (xp + y)^A = {}_A C_0(xp)^A + {}_A C_1(xp)^{A-1}(y)^{1} + \cdots + {}_A C_n(y)^A$$
If we calculate $\bmod{p}$ of the above term we would get $$(r^A) \bmod{p} = 0 + 0 + \cdots + (y^A) \bmod{p} = (y^A) \bmod{p}$$
Similarly, let $y^A = \alpha p + \beta$, then $(y^A) \bmod{p} = \beta$. We have:
$$((r^A) \bmod{p})^B \bmod{p}=((y^A) \bmod{p})^B \bmod{p} = (\beta)^B \bmod{p}$$
Now we would calculate $r^{AB} \bmod{p}$.
$$r^{AB} \bmod{p} = (xp + y)^{AB} \bmod{p} = y^{AB} \bmod{p} \\ = (y^A)^B \bmod{p} = (\alpha p + \beta)^B \bmod{p} = (\beta)^B \bmod{p}$$
i.e.$$((r^A) \bmod{p})^B \bmod{p} = (r^{AB}) \bmod{p} = ((r^B) \bmod{p})^A \bmod{p}$$ -Hence proved