$x^2 \equiv -2,2 \pmod {122}$

I am trying to solve the following problem:

Which of the following congruences has solutions? How many?

$$x^2 \equiv 2 \pmod {122}$$ $$x^2 \equiv -2 \pmod {122}$$

For both congruences, $$122 = 2\times61$$. Hence, each congruence can be decomposed to the following: $$x^2 \equiv 2 \pmod 2$$ and $$x^2 \equiv 2 \pmod{61}$$. For the first one, $$x$$ has a unique solution $$x = 0$$. for the second one, I need to compute $$\left(\frac{2}{61}\right)$$ which is $$-1$$.

Now Can I conclude that the congruence is unsolvable? Hence, there exist no solutions?

For the second problem, the congruence $$x^2 \equiv -2 \pmod {61}$$ is solvable.

Can I conclude that there is one or two solutions?

• Dec 14, 2018 at 11:49
• And yes: from the second non-solvable congruence you can deduce the original one also has no solution. Dec 14, 2018 at 11:56

Let's work with the congruence $$x^2 \equiv -2 \pmod {122}$$.
The ring $$\mathbb Z_{122}$$ is isomorphic to $$\mathbb Z_{2} \times \mathbb Z_{61}$$ by the Chinese Remainder Theorem, as you pointed out. Now applying the isomorphism to both sides, you are looking for a solution to $$(x,x')^2 = (-2,-2)$$ where $$x \in \mathbb Z_2$$ and $$x' \in \mathbb Z_{61}$$.
If $$\left(-2\over 61\right)=1$$ then there are exactly two solutions to $$x^2 \equiv -2 \pmod{61}$$. The reason for that is because $$\mathbb Z_{61}$$ is a field, and the factor theorem: The polynomial $$X^2+2$$ has a unique factorisation $$(X-a)(X-b)$$ where each of $$a$$ and $$b$$ is a root of the polynomial. And the roots must be distinct because if $$a$$ is a root of that polynomial then so is $$-a$$, and the only element of a field that is the negation of itself is $$0$$ (unless the field has characteristic $$2$$).
On the other hand, there is only one solution to $$(x')^2 \equiv -2 \pmod 2$$. So multiplying the number of possible values for $$x$$ and $$x'$$ gives $$2$$.
With the congruence $$x^2 \equiv 2 \pmod {122}$$, use the distributivity of the Legendre symbols. The Legendre symbol of $$-1$$ is easily shown to be $$-1$$ in $$\mathbb Z_{61}$$, showing that no solution is possible.