Past exam of the options II course of the University of Oxford / 2012 / C / C2

For an integer $a$ and an odd prime $p$, the Legendre symbol isThe value one refers to a nonzero quadratic residue; divisibility by $p$ is recorded separately by zero.

Euler's criterion states thatFor $p\nmid a$ this says that the power is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue. When $p\mid a$, both sides are zero modulo $p$.

Euler's criterion givesIf either factor is divisible by $p$, both asserted values are zero. Otherwise the two values lie in $\{1,-1\}$, whose elements are distinct modulo an odd prime. The modular congruence is therefore equality:Finally, $a\equiv b(\mathrm{mod}p)$ means they give the same residue class and thus the same set of square-congruence solutions. Divisibility by $p$ is also identical. Hence $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.

The quadratic reciprocity states that for distinct odd primes $p,q$,With $q=3$, it gives $\left(\frac{3}{p}\right)=(-1{)}^{(p-1)/2}\left(\frac{p}{3}\right)$. The nonzero square modulo three is one, so $\left(\frac{p}{3}\right)=1$ when $p\equiv 1(\mathrm{mod}3)$, and $-1$ when $p\equiv -1(\mathrm{mod}3)$. An odd prime other than three is congruent to $1,5,7$, or $11$ modulo twelve. Evaluating the two signs givesThus

Reducing modulo $23$ gives $189\equiv 5$. Reciprocity with five has positive sign, sosince the nonzero squares modulo five are one and four. Modulo $59$, $189\equiv 12=4\cdot 3$, and $59\equiv -1(\mathrm{mod}12)$. Thus part (b) givesAs $1357=23\cdot 59$, a solution modulo $1357$ would in particular solve the modular congruence modulo $23$, contradicting the first symbol. Therefore there is no integer solution modulo $1357$.