Exercise 3.3.3 (Solvable congruences (2))

Proof. The integers $61,97,79,103$ are prime numbers.

(a)

Since $\left(\frac{11}{61}\right)=-1$, the congruence $x^2\equiv 11(\mathit{mod}61)$ is not solvable.

(b)

Since $\left(\frac{42}{97}\right)=-1$, the congruence $x^2\equiv 42(\mathit{mod}97)$ is not solvable.

(c)

Since $\left(\frac{-43}{79}\right)=1$, the congruence $x^2\equiv -43(\mathit{mod}79)$ is solvable.

( $-43\equiv 36(\mathit{mod}79)$, so the solutions are $6,73$.)

(d)

Since $\left(\frac{31}{103}\right)=-1$, the congruence $x^2-31\equiv 0(\mathit{mod}103)$ is not solvable.