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

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?

• Comments are not for extended discussion; this conversation has been moved to chat.
– Pedro
Commented Oct 13, 2021 at 12:02

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

• would you mind explaining it sufficiently?? Commented Oct 12, 2021 at 9:18
• @Spectre $p$ prime, then $x^2 \equiv a^2 \pmod{p} \iff p|x^2-a^2 \iff p|(x-a)(x+a) \iff p|x-a$ or $p|x+a \iff x \equiv \pm a \pmod{p}$ by Euclid's lemma. Commented Oct 12, 2021 at 9:22
• @Adola Now how to solve these equations,we need to consider $4$ different cases and solve? Commented Oct 13, 2021 at 4:34
• @KishalaySarkar. Yes. There's a shortcut on two cases. Case 1: x = 1 mod 5, x = 1 mod 4, x = 0 mod 3 then from the first and second, x = 1 mod 20. combining with x = 0 mod 3 we have x = 21 mod 60 Case 2: x = -1 mod 5, x = -1 mod 4, x = 0 mod 3 then from the first and second, x = -1 mod 20. combining with x = 0 mod 3 we have x = 39 mod 60 Commented Oct 13, 2021 at 12:54

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}

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

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

• This is not a clever way I think. Commented Oct 12, 2021 at 8:34
• Note that, no calculations are required at the end. The number $n$ must end with $9$. From here we get the possible set $n\in\left\{3,7,13,17\right\}.$ Thus, it is enough to check these mumbers. Commented Oct 12, 2021 at 12:05
• Yes, this is very good! Commented Oct 12, 2021 at 12:15
• @TereseLisbon Thank you very much for taking your time to review. This is very precious to me. $( ◜‿◝ )$ Commented Oct 12, 2021 at 12:42