## Online Course Discussion Forum

### MC II-A Number Theory 5.16

For this question I don't get why we need M bigger or equal to 5 and M=8=5+3. It looks confusing. Could you please offer some additional explanation? Thanks.

The basic idea is we want to test $N\geq 500$ until we get the smallest $N$ so that $N^2 \equiv 1 \pmod{9}$.

The key idea of modular arithmetic, however, is that we can always replace numbers by their remainders to make our life easier. Hence,

- $500^2 \equiv 5^2 \equiv 7 \pmod{9}$
- $501^2 \equiv 6^2 \equiv 0 \pmod{9}$
- $502^2 \equiv 7^2 \equiv 4 \pmod{9}$
- $503^2 \equiv 8^2 \equiv 1 \pmod{9}$

(Check these calculations yourself to make sure they make sense!)

Taking a step back, once we know that $500\equiv 5 \pmod{9}$, we can just work with the $5$, $6$, $7$, $8$ to find the square that is $1$ mod $9$. That's what the solution idea is talking about with the $M$ values.

Hope this helps!

Social networks