I was watching a video on the Diffie-Hellman key exchange, and they did:
$$12 ^{15}\bmod \ 17 = 6 ^{13}\bmod \ 17$$ because
$$3 ^{13}\bmod \ 17 = 12$$
So he substituted $3^{13}$ in for $12$.
$$3 ^{15}\bmod \ 17 = 6$$ So he substituted $3^{15}$ in for $6$.
So I'm new to modular arithmetic, and I was trying to figure out why this works by doing a different example:
$$5^4\bmod \ 17 = 13$$
$$5^{4^7}\bmod \ 17 = 1$$
But... $$13^7\bmod \ 17 = 4$$
I thought they should be congruent. Is there any way you could explain, to me, who doesn't know much about modular arithmetic, why this thinking is wrong?
From the original example, we have
$$3^{13\times15}=(3^{13})^{15}=(3^{15})^{13}$$
When we consider this modulo $17$, we are allowed to replace $3^n$ with $3^n\mod 17$. So by that last part of the above equality, we have
$$(3^{13}\mod 17)^{15}\equiv(3^{15}\mod17)^{13}\pmod{17}$$
In your example, we should have
$$(5^4)^7=(5^7)^4$$
Now, we have $5^4\equiv13\pmod{17}$ and $5^7\equiv10\pmod{17}$.
So we should have $13^7\equiv10^4\pmod{17}$. And, sure enough,
$$13^7\equiv10^4\equiv4\pmod{17}$$