Submitted by Sherlockist on Sun, 04/08/2018 - 03:24
Forums:
I am confused by the mod calculation, could someone help me out?
I understand the reason why for example 14≡2≡-1 (mod 3)
However in the answer sheet, there are some operations without explanations which I cannot catch the idea.
Examples are:
2^n ≡ (-1)^n (mod 3)
125^m ≡ (-1)^n (mod 9)
5^n ≡ (-2)^n (mod 7)
when I take n as number in, I know the equation is right, but I don't know why the equation is satisfied.
If you ask me 5^n ≡ ? (mod 7), I won't be able to figure out by myself.
Mods
At the start of the assignment you were introduced to the relationship:
\[
N_1N_2 \text{ mod }a = n_1n_2 \text{ mod }a
\]
(Where $N_1=n_1 \text{ mod } a$ etc.)
We have $5=-2 \text{ mod } 7$ (Easiest to see if you think of a "clock" with positions 0, 1, 2, 3, 4, 5, 6, then going 5 "clockwise" is the same as going 2 "anticlockwise" - sketch it to convince yourself)
Then we have:
\[
5^n \text{ mod } 7 = 5 \times 5 \times \cdots \times 5 \text{ mod } 7\\
=(-2) \times (-2) \times \cdots \times (-2) \text{ mod } 7\\
=(-2)^n \text{ mod } 7
\]