Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / C (Number Theory)

A square residue modulo $p$ is a congruence class represented by $x^2$ for some integer $x$. For the final all-primes solvability statement, zero is included as a square. The Legendre symbol distinguishes the zero class from the nonzero square and nonsquare classes:When the term quadratic residue is reserved for nonzero classes, the zero case must be stated separately, as in this definition.

Euler's criterion states that, for an odd prime $p$ and $p\nmid a$,Thus this power is congruent to one for a nonzero square and to minus one for a nonsquare. The congruence also holds when $p\mid a$ if both sides are taken to be zero.

For distinct odd primes $p,q$, quadratic reciprocity isThe usual supplementary laws areThe first supplement also follows immediately by inserting $a=-1$ into Euler's criterion.

If $p$ divides $a$ or $b$, it divides their product and both sides of the proposed identity are zero. Otherwise use Euler's criterion and the ordinary exponent rule:Both sides are in $\{1,-1\}$, and these two values are distinct modulo the odd prime $p$. Hence the congruence is an equality:

For odd $m,n$,The last term is even, so induction over the prime factors, including repetitions, gives $\frac{b-1}{2}\equiv {\sum }_i\frac{p_i-1}{2}(\mathrm{mod}2)$. Using the first supplementary law in each Legendre factor,For $b=1$, the product is empty and both sides equal one.

If $b,c$ have a common prime factor, both Jacobi symbols are zero, and the identity holds. Otherwise write $b={\prod }_i{p}_i$, $c={\prod }_j{q}_j$ with multiplicity. All cross-pairs of primes are distinct. Multiplying quadratic reciprocity over these pairs givesThe exponent factors as a product of two sums. The parity identity from part (i) makes it congruent modulo two to $[(b-1)/2][(c-1)/2]$. ThereforeThe same formula includes a denominator equal to one by the empty-product convention.

Because $a=-b^2$ is odd, $b$ is odd. Choose $k=4b^2-1$, a positive integer congruent to three modulo four. Also $\gcd (k,b)=1$, so the square $b^2$ has Jacobi symbol one modulo $k$. Multiplicativity in the numerator follows from the corresponding Legendre property in each prime factor. ThusThis gives an explicit positive odd denominator with the required obstruction.

Choose a nonzero quadratic nonresidue $c$ modulo $q$. By the Chinese remainder theorem, choose a positive integer $k$ satisfyingThe moduli are pairwise coprime, and $k$ is coprime to $qb$. Jacobi reciprocity, with $k\equiv 1(\mathrm{mod}4)$, givesSince $t$ is odd, multiplying these symbols yieldsWhen $b=1$ its congruence imposes no restriction and its Jacobi factor equals one.

An integer square is a square modulo every prime, with the zero class allowed at primes dividing the integer. Conversely, suppose an odd integer $a$ is not an integer square. If every prime exponent in $|a|$ is even, the nonsquare condition forces $a=-b^2$, handled by part (i). Otherwise some odd prime has an odd exponent, so $a=\pm q^{t}b$ as in part (ii). In either case there is a positive odd $k$ with $(a/k)=-1$.

Factor $k$ into odd primes. A product of Legendre symbols equalling minus one has at least one factor equal to minus one. Thus $a$ fails to be a square modulo one of those primes, contradicting the hypothesis. HenceThe solvability formulation makes explicit the zero-residue convention needed by the printed final assertion. The prime two causes no extra issue because every odd integer is one modulo two.