How to check if the quadratic congruence has solution or not

Question

How to check if the quadratic congruence has solution or not, for example check: $$x^2\equiv 1141 \pmod{2020}$$

I use Euler's Criterion but it doesn't work: $$1141^\dfrac{2020-1}{2} \equiv 1 \pmod{2020}$$ Because $\dfrac{2020-1}{2}$ is a decimal number. Any hints would be great!

Answer 1

By the Chinese Remainder Theorem, since $2020=20\cdot 101$, it is enough to check whether the equation has roots modulo $20$ and $101$.

Modulo $20$: $x=1$ is a solution.

Modulo $101$: The equation is $x^2\equiv 30\pmod{101}$. Now, the quadratic residue is \begin{align} \left(\frac{30}{101}\right)&=\left(\frac{2}{101}\right)\left(\frac{3}{101}\right)\left(\frac{5}{101}\right)\\ &=(-1)^{\frac{101^2-1}8}\left(\frac{101}{3}\right)\left(\frac{101}{5}\right)\\ &=(-1)(-1)1\\ &=1. \end{align}

Thus, there is a solution.

P.S.: $x=139$ is a solution to the original congruence.

Answer 2

$x^2\equiv 1141 mod (2020)$

$1141=163\times 7$

$2020=20\times 101$

$163^{100}=(163^{50})^2\equiv 1 mod (101)$

$7^{100}\equiv 1 mod (101)$

$1141^{100} \equiv 1 mod (101)$

$\phi (20)= 8$

$1141^8=(1141^4)^2 \equiv 1 mod (20)$

So $x^2\equiv 1 mod (2020)$

Which means there is a solution.