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!