<s>[INST] What are the steps to simplify the following modulus expression? I have no clue how to do this exactly. Is there a systematic way of doing this or you just have to do it by trial and error?
$n^2 \equiv 9 \pmod {72}$
to $n \equiv a \pmod b$?
 [/INST] Note that $72=8\cdot 9$ and that $n^2\equiv 9\pmod{72}$ implies (and is in fact equivalent to) $n^2\equiv 9\pmod 9$ and $n^2\equiv 9\pmod 8$.
The first simplifies to $n^2\equiv 0\pmod 9$, i.e. $3^2|n^2$. This is equivalent to $3|n$. The other equation simplifieds to $n^2 \equiv 1\pmod 8$. You may try these few cass by hand, but one should know this special property of the prime $2$:


*

*The square of an even number is always $\equiv 0\pmod 4$

*The square of an odd number is always $\equiv 1\pmod 8$


Thus  $n^2\equiv 9\pmod{72}$ is the same as $n\equiv 0\pmod 3$ and $n\equiv 1\pmod 2$, i.e. $$n\equiv 3\pmod 6.$$
Check: If $n=6k+3$, then $n^2=36 k^2+36 k + 9=36\cdot k(k+1)+9$. Since one od the numbers $k, k+1$ is even, $k(k+1)$ is even and $36k(k+1)$ is a multiple of $72$.
</s>