\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(i)]
Explaining your reasoning carefully, prove that both 311 and 317
are primes.

\item[(ii)]
Stating clearly the theoretical results you have used, calculate
the Legendre symbol

$$\left(\frac{317}{311}\right).$$

(Hint: You may assume that, if $p$ is an odd prime, 2 is a square
mod ($p$) if and only if $p\equiv\pm1$ mod (8).)

\end{description}



ANSWER

\begin{description}

\item[(i)]
Since $18^2=324, \sqrt{311}$ and $\sqrt{317}$ are both strictly
smaller than 18. Hence, by Eratosthenes observation, we have only
to verify that no prime among 2,3,5,7,11,13,17 divides 311 or 317.
Clearly 2 does not divide any odd number. Since 3+1+1=5 and
3+1+7=11 are not divisible by 3, 3 does not divide either number.
Neither ends in 0 or 5 so 5 does not divide either number. Since
$7\times 45=315$ w see that 7 does not divide either number. Since
$3-1+1=3$ and $3-1+7=9$ are not divisible by 11, 11 does not
divide either number. Finally, since $17\times19=323$, 17 does not
divide either number.

\item[(ii)]
The following succession of Legender symbols are equal:

$$\left(\frac{317}{311}\right)=\left(\frac{6}{311}\right)$$

since $317\equiv6$ mod (311). Then

$$\left(\frac{6}{311}\right)=\left(\frac{2}{311}\right)\left(\frac{3}{311}\right)$$

by multiplicativity of the Legendre symbol in the top variable.

Next

$$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}$$

for any odd prime. When $p=311=(8\times38)+7$ this is
$(-1)^{(7^2-1)/8}=(-1)^6=1$. Hence we must calculate

$$\left(\frac{3}{311}\right)=\left(\frac{311}{3}\right)(-1)^{(3-1)(311-1)/4}$$

by quadratic reciprocity. However

$$\left(\frac{311}{3}\right)(-1)^{(3-1)(311-1)/4}=-\left(\frac{2}{3}\right)=-(-1)=1.$$

\end{description}




\end{document}