2
$\begingroup$

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?

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

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ would you mind explaining it sufficiently?? $\endgroup$
    – Spectre
    Commented Oct 12, 2021 at 9:18
  • 2
    $\begingroup$ @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. $\endgroup$
    – Adola
    Commented Oct 12, 2021 at 9:22
  • $\begingroup$ @Adola Now how to solve these equations,we need to consider $4$ different cases and solve? $\endgroup$ Commented Oct 13, 2021 at 4:34
  • $\begingroup$ @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 $\endgroup$
    – Adola
    Commented Oct 13, 2021 at 12:54
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This is not a clever way I think. $\endgroup$ Commented Oct 12, 2021 at 8:34
  • $\begingroup$ 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. $\endgroup$ Commented Oct 12, 2021 at 12:05
  • $\begingroup$ Yes, this is very good! $\endgroup$ Commented Oct 12, 2021 at 12:15
  • 1
    $\begingroup$ @TereseLisbon Thank you very much for taking your time to review. This is very precious to me. $( ◜‿◝ )$ $\endgroup$ Commented Oct 12, 2021 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .