0

I believe that this:

$$(5^3 \mod{57})^5 \mod{57}$$

is the same as:

$$(5^3)^5 \mod{57}$$

But what is the logic of this simplification?

Yulian Kraynyak
  • 103
whytheq
  • 237
  • 1
  • 7
  • 12
  • 2
    $(a+kp)^n = a^n + $multiples of $p$ –  Apr 25 '17 at 11:04
  • I've added parentheses to your second formula; the usual convention is that a^b^c is grouped from right to left: as a^(b^c), which is presumably not what you mean. –  Apr 25 '17 at 11:07

2 Answers2

1

Indeed it is, yes. The logic is that taking modulo can be exchanged with multiplication, i.e. $$a \cdot b \mod{c} = (a \mod{c}) \cdot (b \mod{c}) \mod{c}$$ for all $a,b,c$.

This claim can be proven for example using Euclidean division. Then applying this result multiple times, one can show through induction that it also holds for powers.

edit due to the comment: Let's first assume the identity above is true. Now to apply it to your problem, we use it multiple times: What you want to show is that $$(5^3 \mod{57})^5 \mod{57} = (5^3)^5 \mod{57}.$$

For that, we first look at the left hand side: $$(5^3 \mod{57})^5 \mod{57}$$ $$= \left[(5^3 \mod{57})\cdot (5^3 \mod{57})\cdot (5^3 \mod{57})\cdot (5^3 \mod{57})\cdot (5^3 \mod{57})\right]\mod{57}$$

Now applying the above formula multiple times (reading it from right to left), we can draw this together to be $$(5^3 \cdot 5^3 \cdot 5^3 \cdot 5^3 \cdot 5^3) \mod{57}$$ which is simply $$(5^3)^5 \mod{57}.$$

Just in case, also some ideas on how to prove the identity: Let $a,b,c$ be integers. Write $a = rc + (a\mod{c})$ for some $r$ and $b = sc + (b\mod{c})$ for some $s$. That such integers $r,s$ exist is basically the definition of modulo. Now we can compute $$a\cdot b = (rc + (a\mod{c})) (\cdot sc + (b\mod{c}))$$ $$ = rsc^2 + (a\mod{c})c + (b\mod{c})c + (a\mod{c})(b\mod{c}).$$ If we now look at it mod $c$, you will notice that all but the last term contain a $c$ as a factor, so they all cancel out mod $c$. What is left is then exactly the identity.

Dirk
  • 6,359
  • although I'm still struggling using your identity to show they are the same - would you be able to spell it out a little further for someone is not a mathematician? Could you take a small example like this (5^2 mod 3)^3 mod 3 and use your identity to get to 5^6 mod 3 ? – whytheq Apr 27 '17 at 12:42
  • thanks for the extra detail: I now understand! The trick behind Diffie-Hellman key exchange is now a lot clearer – whytheq Apr 27 '17 at 15:15
1

In general, $$(a^b)^c=a^{bc}$$ and not $$a^{b^c}=(a^b)^c$$

Similarly for modular arithmetic.

So, $$(5^3)^5\equiv5^{3\cdot5}\pmod{57}$$

Now as $57=3\cdot19,$ we should find $5^{15}\pmod3,5^{15}\pmod{19}$ separately.

Then apply Chinese Remainder Theorem.

lab bhattacharjee
  • 274,582