Exercise 3.3.2 (Solvable congruences (1))

Proof.

(a)

Since $127$ is a prime number, the congruence $x^2\equiv 10(\mathit{mod}127)$ has a solution if and only if $\left(\frac{10}{127}\right)=1$. Moreover $$\left(\frac{10}{127}\right)=\left(\frac{2}{127}\right)\left(\frac{5}{127}\right)=\left(\frac{5}{127}\right)=\left(\frac{127}{5}\right)=\left(\frac{2}{5}\right)=-1.$$

Therefore the congruence $x^2\equiv 10(\mathit{mod}127)$ has no solution.

(b)

Here $173$ is a prime number, and $\left(\frac{73}{173}\right)=1.$ Therefore the congruence $x^2\equiv 73(\mathit{mod}173)$ is solvable. (The solutions are $65,108$.)

(c)

Here $401$ is also a prime number, and $\left(\frac{137}{401}\right)=-1$. Therefore the congruence $x^2\equiv 137(\mathit{mod}401)$ is not solvable.