Exercise 3.1.7 (Solve $x^2 \equiv \pm 2 \pmod m$ for $m = 61,59,118,122$)

Proof. Here $61$ and $59$ are prime numbers.

(a)

Since $61=7\times 8+5$ is of the form $8k+5$, $\left(\frac{2}{61}\right)=-1$ by Theorem 3.3. Therefore the congruence $x^2\equiv 2(\mathit{mod}61)$ has no solution.

(b)

Since $59=7\times 8+3$ is of the form $8k+3$, $\left(\frac{2}{59}\right)=-1$. Therefore the congruence $x^2\equiv 2(\mathit{mod}59)$ has no solution.

(c)

Since $\left(\frac{-2}{61}\right)=\left(\frac{-1}{61}\right)\left(\frac{2}{61}\right)=-{(-1)}^{(61-1)∕2}=-1$, the congruence $x^2\equiv -2(\mathit{mod}61)$ has no solution.

(d)

Here $\left(\frac{-2}{59}\right)=\left(\frac{-1}{59}\right)\left(\frac{2}{59}\right)=-{(-1)}^{(59-1)∕2}=1$. Therefore $x^2\equiv -1(\mathit{mod}59)$ has $2$ solutions.

(With the RESSOL (Tonelli-Shanks) algorithm, we obtain the solutions $23,36$ modulo $59$.)

(e)

Here $122=2\cdot 61$. If $x^2\equiv 2(\mathit{mod}122)$, a fortiori $x^2\equiv 2(\mathit{mod}61)$, but this last congruence has no solution by part (a). Therefore the congruence $x^2\equiv 2(\mathit{mod}122)$ has no solution.

(f)

Here $118=2\cdot 59$. With the same reasoning, since $x^2\equiv 2(\mathit{mod}59)$ has no solution by part (b), the congruence $x^2\equiv 2(\mathit{mod}118)$ has no solution.

(g)

Since $x^2\equiv -2(\mathit{mod}61)$ has no solution by part (c), the congruence $x^2\equiv -2(\mathit{mod}122)$ has no solution.

(h)

The congruence $x^2\equiv -2(\mathit{mod}118)$ is equivalent to $$\begin{array}{lll}\hfill \{\begin{array}{cc}{x}^2\equiv -2\hfill & (\mathit{mod}2),\hfill \\ x^2\equiv -2\hfill & (\mathit{mod}59),\hfill \end{array}& & \hfill \text{(1)}\end{array}$$

Then (1) is equivalent to

$$\begin{array}{lll}\hfill \{\begin{array}{cc}x\equiv 0\hfill & (\mathit{mod}2),\hfill \\ x\equiv -36\hfill & (\mathit{mod}59),\hfill \end{array}\text{ or }\{\begin{array}{cc}x\equiv 0\hfill & (\mathit{mod}2),\hfill \\ x\equiv 36\hfill & (\mathit{mod}59).\hfill \end{array}& & \hfill \end{array}$$

Therefore the solutions of $x^2\equiv -2(\mathit{mod}118)$ are $x\equiv -36\equiv 82(\mathit{mod}118)$ or $x\equiv 36(\mathit{mod}118)$ ( $2$ solutions).

Verification:

     sage: [a for a in Integers(118) if a^2 == Mod(-2,118)]
     [36, 82]