Here the solution for $27^{17} \pmod{15}$ is shown.
Why is $27 \equiv 12 \pmod{15}$ rewritten as $27 \equiv -3 \pmod{15}$?
What is the logic/proof?
Asked
Active
Viewed 1,866 times
1
-
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. – Mar 24 '14 at 23:01
-
Hint $\ {\rm mod}\ m!:,\ a\equiv a!-!m\ \ $ – Bill Dubuque Mar 24 '14 at 23:11
1 Answers
3
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}$
Yiyuan Lee
- 14,435