1

Why is (x mod n)^y mod n == x^y mod n? It seems to me like there is a property in modular arithmetic that explains why, does anyone have a simple way of explaining it?

J. Doe
  • 11
  • 2
    Hint: just show that $(x+n)^y\equiv x^y\pmod n$. The binomial theorem might help. – lulu Nov 13 '18 at 12:53
  • It's possible that your comment made me understand it. Will let it bake a bit, and see if I connected the dots. – J. Doe Nov 13 '18 at 13:56

1 Answers1

1

Let $$g^{k_1}=nq_1+r$$therefore$$(g^{k1}\mod n)^{k2} \mod n=r^{k_2}\mod n$$Furthermore:$$(g^{k_1})^{k_2}\mod n=(nq+r)^{k_2}\mod n=nq_2+r^{k_2}\mod n=r^{k_2}\mod n$$therefore$$(g^{k1}\mod n)^{k2} \mod n=(g^{k_1})^{k_2}\mod n$$

Mostafa Ayaz
  • 31,924