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

For an odd prime number $p$, a nonzero class $a(\mathrm{mod}p)$ is a quadratic residue if $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$ not divisible by $p$. The Legendre symbol isWhen discussing solvability of $x^2\equiv a(\mathrm{mod}p)$ without a coprimality assumption, zero is also a square. This convention matters in the final local characterization of integer squares.

The Euler criterion states that for an odd prime number $p$ and $p\nmid a$,The same modular congruence remains true when $p\mid a$, with both sides zero.

For distinct odd primes $p$ and $q$, quadratic reciprocity statesThe supplementary laws are

If $p$ divides $a$ or $b$, both sides of the claimed multiplicativity identity are zero. Otherwise the Euler criterion givesEach side is $1$ or $-1$. Since $p$ is odd, these two integers represent different residue classes. Hence the modular congruence gives equality:

For odd $m,n$,is even. Induction over the prime factors of $b$, repeated according to multiplicity, therefore givesUsing the supplementary law for each Legendre symbol in the definition of the Jacobi symbol,For $b=1$, the empty product and the displayed expression are both $1$.

If $\gcd (b,c)>1$, both Jacobi symbols vanish, so the formula holds. Otherwise write $b={\prod }_i{p}_i$ and $c={\prod }_j{q}_j$, retaining repeated factors. Multiplicativity of the Jacobi symbol and quadratic reciprocity giveThe exponent isby the parity identity from part (i). The product of the reversed Legendre symbols is $(c/b)$. Thus the Jacobi reciprocity law isThis also covers $b=1$ or $c=1$ by empty products.

Here $b$ is odd and nonzero. Choose $k=4|b|-1$. This is a positive odd integer, $k\equiv 3(\mathrm{mod}4)$, and $\gcd (k,b)=1$. By multiplicativity of the Jacobi symbol,The coprimality condition ensures that the squared Jacobi symbol is $1$ rather than $0$.

Choose a nonzero quadratic nonresidue $c(\mathrm{mod}q)$. There is one because the squaring map on ${\mathbb{F}}_q^{\times }$ is two-to-one, so exactly half its elements are squares. The moduli $4,q,b$ are pairwise coprime, so the Chinese remainder theorem gives a positive integer $k$ satisfyingWhen $b=1$, the last condition is vacuous. In particular $k$ is odd and coprime to $qb$. Since $k\equiv 1(\mathrm{mod}4)$, Jacobi reciprocity givesAs $t$ is odd, multiplicativity of the Jacobi symbol now yields

Every integer square remains a square modulo every prime number, including the zero class at its prime divisors. Conversely, let $a$ be an odd integer which is not an integer square. If $a$ is the negative of a square, part (i) supplies an odd $k$ with $(a/k)=-1$. In every other case, the prime factorization of $|a|$ has an odd exponent $t$ at some odd prime $q$. Write $a=\pm q^{t}b$ with $b>0$ odd and $\gcd (q,b)=1$, and apply part (ii).

In either case, factor the resulting $k$ into primes. Since its Jacobi symbol is a product of Legendre symbols and equals $-1$, at least one prime factor $p$ has $(a/p)=-1$. Thus $a$ is not a square modulo that prime. This proves an odd integer is an integer square exactly when it is a square modulo every prime. If the phrase quadratic residue is restricted to nonzero residue classes, the final statement must instead say “a square modulo every prime”; for example, $9$ reduces to zero modulo $3$.