1
$\begingroup$

Here the solution for $27^{17} \pmod{15}$ is shown.

enter image description here

Why is $27 \equiv 12 \pmod{15}$ rewritten as $27 \equiv -3 \pmod{15}$?

What is the logic/proof?

$\endgroup$
  • $\begingroup$ Since $12 - (-3)$ is divisible by $5$, the congruence is valid. It's just done to use smaller numbers, which are easier to compute with. $\endgroup$ – user61527 Mar 24 '14 at 23:01
  • $\begingroup$ Hint $\ {\rm mod}\ m\!:\,\ a\equiv a\!-\!m\ \ $ $\endgroup$ – Bill Dubuque Mar 24 '14 at 23:11
3
$\begingroup$

It can be proved by arguing that $15| (27-12)$ and $15|(27-(-3))$.

This is because in general, $$a\equiv b \pmod{n} \iff n|(a-b)$$

We can use this to show that $$a \equiv a-n \pmod{n}$$

This can be applied to your case : $27 \equiv 27-15=12 \pmod {15}$ and $12\equiv 12-15=-3\pmod{15}$

$\endgroup$

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.