Trouble with substitution in modular arithmetic.

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?

• $5^{4^7}\neq (5^4)^7$ – David Peterson Mar 25 '16 at 5:47

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)^{15}\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}$$

• Thanks! I'm wondering if there's a congruence property that says thar we can replace 3^n with 3^n mod 17. – rb612 Mar 27 '16 at 2:02
• @rb612 You know the rule for multiplication? Exponentiation is just repeated multiplication. – Mike Mar 27 '16 at 13:49
• Makes sense! Thanks! – rb612 Mar 27 '16 at 18:41