Does $x^2 \equiv 211\pmod{ 159}$ have a solution?

Question

Note that 159=3*53. The answer to this question is yes. I managed to find two of the solutions. They are $x=23,136$ but there are two more. The main question that I have is whether there is an easier way to find all solutions of a quadratic congruence when the modulus is not prime. Is it always the case that there will be four solutions when the modulus is composite? By solutions I mean the least residues. Thank you!

Answer 1

If you know how to find the solutions when the modulus is prime, then, when the modulus is composite, solve the congruence modulo the primes, and use the Chinese Remainder Theorem to put them together to get solutions modulo the composites.

The number of solutions is (give or take a few exceptional circumstances) $2^r$, where $r$ is the number of distinct primes dividing the modulus. In your case, there are 2 solutions modulo 3, and 2 solutions modulo 53, yielding 4 solutions modulo 159.

Answer 2

Note that $159=3\cdot 53$. If the congruences $x^2\equiv 211\pmod{3}$ and $x^2\equiv 211\pmod{53}$ have solutions $x\equiv a \pmod{3}$ and $x\equiv b\pmod{53}$, then by the Chinese Remainder Theorem we can find an $x$ such that $x\equiv a \pmod{3}$ and $x\equiv b \pmod{53}$. Such an $x$ will have the property that $x^2\equiv 211\pmod{159}$.

To show that $x^2\equiv 1 \pmod{3}$ has a solution is trivial.

So we look at $x^2\equiv 211\pmod{53}$. We can find an explicit solution. But it is easier to note that $211\equiv -1\pmod{53}$. And $x^2\equiv -1 \pmod{53}$ has a solution, since $53$ is a prime of the form $4k+1$.

Answer 3

Till now we have found,

(i) we need to find x such that $x^2≡211(mod\ 3)$ and $x^2≡211(mod\ 53)$

(ii)$ \ x^2≡211(mod\ 3)≡1\pmod 3=>x≡±1\pmod 3=3y±1$ , for some integer $y$.

(iii)$ \ x^2≡211\pmod {53}≡-1\pmod {53}$ which is clearly solvable(applying Euler's criterion)

Now I am going to find the solution of (iii):

As $53=7^2+2^2$, so $53(c^2+d^2)=(7^2+2^2)(c^2+d^2)=(7c±2d)^2+(7d∓2c)^2$ for some integers $c,d$.

Comparing with $x^2+1$, the possible values of $(x,1)$ are $(±(7c-2d), ±(7d+2c))$ or $(±(7d+2c), ±(7c-2d))$

If we take $7c-2d=1$ and $7d+2c=x$, then $7c-2d=1=7-3.2\Rightarrow 7(c-1)=2(d-3)\Rightarrow 7|(d-3)$ and $2|(c-1)$

i.e., $\frac{d-3}{7}=\frac{c-1}{2}=b$, where $b$ is an integer.

$\Rightarrow d=7b+3$ and $c=2b+1\Rightarrow x=7d+2c=7(7b+3)+2(2b+1)=53b+23$

$\Rightarrow 23$ is a solution of $x^2≡-1\pmod {53}$

Now, if A is a solution of $x^2≡t\pmod m\Rightarrow A^2≡t\pmod m\Rightarrow (-A)^2\equiv t\pmod m$ so, $(-A)$ will be another solution $\rightarrow (1)$.

So, $-23$ is a solution of $x^2≡-1(mod\ 53)$

$\Rightarrow x=53z±23$, for some integer $z$.

Other combinations of values of $(x,1)$ will reach at the same point.

Now we need to solve $53z±23=3y±1$

Taking both signs as positive, $53z+23=3y+1$

$=>3y-53z=22=22(53.2-3.35)$ as 53.2-3.35=1

$=>3(y+22.35)=53(z+2.22)$

$=>3|(z+44)=>3|(z-1)=>z=3w+1$ for some integer w.

$=>x=53z+23=53(3w+1)+23=159w+76≡76(mod\ 159)$

So, -76 will also be another solution (using (1)).

Now taking, $53z-23=3y+1$

$=>53z=3(y+8)=>3|z=>z=3u$ for some integer u.

$=>x=53z-23=53(3u)-23≡-23(mod\ 159)$

So, 23 will also be another solution (using (1)).

So, the 4 solutions are ±23, ±76.

Some generalization : As we know, any prime(p) of the form 4m+1 can always be expressed as $a^2+b^2$.

We observe, $(a,b) > a^2+b^2$ and $ (a,b) |(a^2+b^2) $

If $(a,b)>1,\ a^2+b^2$ can not be prime, but as $p(=a^2+b^2)$ is prime, (a,b) must be 1.

So, we can always find p,q in integers, such that $p\cdot a+q\cdot b=1$.

x can be calculated as $p\cdot b-q\cdot a$ as a,b are given.