# 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$?

-

$n^2\equiv9\pmod{72}$ iff $72\mid n^2-9$, i.e., iff $n^2-9=72k$ for some integer $k$. Then $n^2=72k+9$ is divisible by $9$ and hence by $3$. Since $3$ is prime, this implies that $3\mid n$, and we can write $n=3m$ for some integer $m$. Now we have $9m^2=72k+9$, or $m^2=8k+1$, i.e., $m^2\equiv1\pmod 8$. It’s staightforward to verify that this congruence is satisfied precisely when $m$ is odd, say $m=2\ell+1$. Thus, the full set of solutions is given by $n=3m=3(2\ell+1)=6\ell+3$, which can be rewritten as the congruence $n\equiv3\pmod6$.

With more experience you would know that since $72=8\cdot9$, the congruence $n^2\equiv9\pmod{72}$ implies the congruences $n^2\equiv9\pmod8$ and $n^2\equiv9\pmod9$ and could start working with them immediately. (In fact $n^2\equiv9\pmod{72}$ is equivalent to the conjunction of $n^2\equiv9\pmod8$ and $n^2\equiv9\pmod9$, since $\gcd(8,9)=1$.)

-

Note that $n^2\equiv 9 \pmod {72}$ is equivalent to $$(n-3)(n+3)\equiv 0 \pmod {72}$$ So it is sufficient to solve the simultaneous congruences $$(n-3)(n+3)=0\pmod 8$$ and $$(n-3)(n+3)\equiv 0 \pmod 9$$ The second congruence is true iff $n$ is divisible by $3$, because then both $n-3$ and $n+3$ are divisible by $3$, so their product is divisible by $9$. If $n$ is not divisible by $3$, then neither $n-3$ nor $n+3$ is divisible by $3$, so their product isn't. Thus, $n\equiv 0 \mod 3$. In the first congruence, we similarly obtain that $n$ must be odd. We claim that this is also sufficient. Indeed, since clearly $n-3$ and $n+3$ are both even, assume that they are both $2 \pmod 4$. This is clearly impossible because they have a difference of $6$. Thus, one of $n-3$ and $n+3$ must be divisible by $4$, and the other is even, so their product is $0 \pmod 8$. Then $n\equiv 1 \pmod 2$. Then, the set of solutions is just all $n$ that satisfies $n\equiv 1\pmod 2$ and $n \equiv 0 \pmod 3$, which is equivalent to $n \equiv 3 \mod 6$.

-

In this case, since $\,9\,$ is a perfect integer square much smaller than $\,72\,$ , the beginning of the solution is pretty straightforward:

$$n^2=9\pmod{72}\Longrightarrow n=\pm 3\pmod {72}$$

But since $\,72\,$ is not a prime there may be other solutions, and in fact we also have, say

$$n^2=9\pmod{72}\Longrightarrow n=\pm 9\pmod{72}$$

-

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$.

-

$n^2 = 72 M + 9 = 9(8M+1)$. Hence, $9 \vert n^2 \implies 3 \vert n$. Hence, $n = 3k$. This gives us that $k^2 = 8M+1 \implies k$ is odd (since any odd square is of the form $8k+1$ and even square is of the form $8k$ or $8k+4$). Hence, $$n = 3(2 \ell + 1) = 6 \ell + 3 \equiv 3 \pmod{6}$$

-

The congruence forces $n$ to be divisible by $3$, so $n=3k$. Then $n^2\equiv 9\pmod{72}$ iff $9k^2\equiv 9\pmod{72}$ iff $k^2\equiv 1\pmod{8}$.

The solutions to this last congruence are $1$, $3$, $5$, $7$ (modulo $8$). This can be expressed more simply as $k\equiv 1\pmod{2}$. Then we get $n=3k\equiv 3\pmod{6}$.

-