Past exam of the short options course of the University of Oxford / 2014 / 1

For an odd prime $p$, the Legendre symbol isIt depends only on the congruence class of the integer $a$. The values $1$ and $-1$ distinguish a nonzero quadratic residue from a quadratic nonresidue; zero is a separate case.

Euler's criterion states, for an odd prime $p$,Apply it to $a=-1$. The integer $(-1{)}^{(p-1)/2}$ is $1$ when $p\equiv 1(\mathrm{mod}4)$ and $-1$ when $p\equiv 3(\mathrm{mod}4)$. Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:This is the first supplementary law for quadratic reciprocity.

Gauss's lemma states that, for $p\nmid a$, if $N$ of the least positive residues of $a,2a,\dots ,((p-1)/2)a$ exceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, with no reduction needed. Write $m=(p-1)/2$. A term $2j$ exceeds $p/2$ exactly when $j>p/4$, soIf $p$ is congruent to $1,3,5,7$ modulo eight, the parity of this count is respectively even, odd, odd, even. Gauss's lemma therefore givesThis proves the second supplementary law for quadratic reciprocity, rather than merely applying it.

Because $p$ is odd, $x$ must be odd. Every odd square is $1$ modulo eight. If $y$ is even, $2y^2$ is zero modulo eight; if $y$ is odd, it is two modulo eight. ThusMore precisely, the first case has even $y$ and the second has odd $y$. These are necessary conditions on the congruence class, as requested; the elementary calculation alone does not prove their sufficiency.

Equivalently, reduction modulo $p$ makes $-2$ a quadratic residue: $p$ cannot divide $y$, since that would also force $p\mid x$ and hence $p^2\mid p$. The two supplementary laws and multiplicativity of the Legendre symbol give the same two allowed classes.

Writing $a=21r$, the second condition becomes $r\equiv 4(\mathrm{mod}5)$. Writing $b=15s$, its second condition becomes $s\equiv 6(\mathrm{mod}7)$. Consequentlygives an infinite set of positive integer solutions. Conversely these are the positive solutions in the indicated congruence classes, by the Chinese remainder theorem.

Choose any pair $(a,b)$ from part (i), and put $A=2^a{3}^b$. The divisibilities of the exponents makepositive integers. Their powers areThus $x^3+y^5=z^7$, with all three powers nonzero and distinct. For example, take $a=84+105t$, $b=90+105t$ for every nonnegative integer $t$. Then $A$ strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity $A+2A=3A$ into three prescribed perfect powers.