\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

For each pair $(a,p)$ below, use Euler's criterion to decide
whether or not the equation $x^2\equiv a$ mod $p$ has any
solutions:-

(i) (2,5)\hspace{1.5cm} (ii) (3,13)\hspace{1.5cm} (iii) (7,31).



ANSWER

\begin{description}

\item[(i)]
We need to calculate $a^{\frac{(p-2)}{2}}$ mod $p$, i.e. $2^2$ mod
5. Now $2^2\equiv-1$ mod 5, so $x^2\equiv2$ mod 5 has no
solutions.

\item[(ii)]
$a^{\frac{(p-1)}{2}}\equiv3^6\equiv(-4)^3\equiv-4.3\equiv-12\equiv1$
mod 13, and so the equation $x^2\equiv3$ mod 13 has two solutions.
(For interest, they are $\pm4$ mod 13.)

\item[(iii)]
$a^{\frac{(p-1)}{2}}\equiv7^{15}$ mod 31. Now
$7^2\equiv49\equiv-13$ mod 31, so $7^3\equiv-91\equiv2$ mod 31.
Thus $7^{15}\equiv2^5\equiv32\equiv1$ mod 31. Thus the equation
$x^2\equiv7$ mod 31 has two solutions. (Actually, $\pm10$ mod 31.)

\end{description}




\end{document}