Determine which of the following congruences are solvable (all moduli are prime):
(a) $x^2 \equiv 12 \pmod {89}$
(b) $x^2 \equiv 40 \pmod {101}$
(c) $x^2 \equiv 36 \pmod {1223}$
(d) $x^2 \equiv 89 \pmod {197}$
(e) $x^2 \equiv 197 \pmod {89}$
(a) The Legendre Symbol tells us whether 12 is a quadratic residue of 89.
$$ (\frac{12}{89}) = (\frac{2^2}{89}) \times (\frac{3}{89}) = (1) \times (\frac{89}{3}) = (\frac{2}{3}) = -1 $$
And so $x^2 \equiv 12 \pmod {89}$ has no integer solutions.
(b) The Legendre Symbol tells us whether 40 is a quadratic residue of 101.
$$ (\frac{40}{101}) = (\frac{2^2}{101}) \times (\frac{2}{101}) \times (\frac{5}{101}) = (1) \times (-1) \times (\frac{101}{5}) = -(\frac{1}{5}) = -1 $$
And so $x^2 \equiv 40 \pmod {101}$ has no integer solutions.
(c) The Legendre Symbol tells us whether 36 is a quadratic residue of 1223.
$$ (\frac{36}{1223}) = (\frac{6^2}{1223}) = 1 $$
And so $x^2 \equiv 36 \pmod {1223}$ does have integer solutions.
(d) The Legendre Symbol tells us whether 89 is a quadratic residue of 197.
$$ (\frac{89}{197}) = (\frac{197}{89}) = (\frac{19}{89})= (\frac{89}{19}) = (\frac{13}{19}) = (\frac{19}{13}) = (\frac{6}{13}) = (\frac{2}{13}) \times (\frac{3}{13}) = (-1) \times (1) = -1$$
And so $x^2 \equiv 89 \pmod {197}$ has no integer solutions.
(e) The Legendre Symbol tells us whether 197 is a quadratic residue of 89.
$$ (\frac{197}{89}) = (\frac{19}{89}) = (\frac{89}{19}) = (\frac{13}{19}) = -1 $$
And so $x^2 \equiv 197 \pmod {89}$ has no integer solutions.
Note that we could have used the Law of Quadratic Reciprocity for this exercise.
$$ (\frac{197}{89}) \times (\frac{89}{197}) = (\frac{197}{89}) \times (-1) = (-1)^{\frac{89-1}{2} \times {\frac{197-1}{2}}} = (-1)^{44 \times 98} = 1 $$
And so $(\frac{197}{89})$ must be -1.