Solve: $x^2\equiv 1 \pmod{20},x^2\equiv 6 \pmod{15},x^2\equiv 9 \pmod{18}.$

Question

I want to solve: $x^2\equiv 1 \pmod{20}, x^2\equiv 6 \pmod {15}, x^2\equiv 9\pmod{18}.$ This is a system of congruence equations, but these are not linear and moduli are not coprime. So,we cannot apply chinese remainder theorem here. However, I think I can solve for $y\equiv 1 \pmod{20}, y\equiv 6 \pmod{15}, y\equiv 9 \pmod{18}$ by using extended chinese remainder theorem,then we have to search for the square numbers out of them.How to do that?

Answer 1

$$x^2 \equiv 1 \pmod{5} \iff x \equiv \pm 1 \pmod{5}$$ $$x^2 \equiv 1 \pmod{4} \iff x \equiv 1,3 \pmod{4}$$ $$x^2 \equiv 0 \pmod{9} \iff x \equiv 0 \pmod{3}$$

Answer 2

Let $m,n,k,r,s\in\mathbb Z_{≥0}^{+}$ then we have,

$$\begin{cases}x^2=20m+1\\ x^2=15n+6\\ x^2=18k+9\end{cases}$$

First restriction:

$$\begin{align} &15n+6=18k+9\\ \implies &5n+2=6k+3\\ \implies &5(n-k)-k=1\\ \implies &k+1=5r\\ \implies &k=5r-1\\ \implies &n=6r-1\\ \end{align}$$

Second restriction:

$$\begin{align}&20m+1=90r-9\\ \implies &20m=10(9r-1)\\ \implies &2m=r+8r-1\\ \implies &r-1=2s\\ \implies &r=2s+1 \\ \implies &m=9s+4\end{align}$$

We conclude that,

$$\begin{align}&m=9s+4\\ &n=12s+5\\ &k=10s+4\end{align}$$

This implies,

$$\begin{align}&x^2=180s+81=9(20s+9)\\\ \implies &u^2=20s+9,\thinspace u\in\mathbb Z^{+}.\end{align}$$

Final answer:

Let $u=20m-n; m,n\in\mathbb Z^{+}$ with $0<n<20$ (we can also write: $x=20m±n; m,n\in\mathbb Z^{+}$ with $0<n<10$)

Then we have,

$$\begin{align}(20m-n)^2-9&\equiv n^2-9\\ &\equiv 0 \thinspace \thinspace \thinspace \text{(mod 20)}\end{align}$$

We see that the number $n^2$ must end with $9$. Thus, we can restrict the $n$, such that

$$n\in\left\{3,7,13,17\right\}$$

Therefore, we obtain the all possible solutions as follows:

$$x=60m-3n,\thinspace n\in\left\{3,7,13,17\right\}.$$