0
$\begingroup$

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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.