2
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I had a mistake in the calculation of legendre symbol. I have updated it and would like to update your answer accordingly. Really thankful. :) $\endgroup$ Dec 14, 2018 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.