Past exam of the short options course of the University of Oxford / 2021 / 1 (Number theory)

No. Take $P=2$, $Q=9$. The Jacobi symbol isbut the squares modulo $3$ are $0,1$. A square root of $2$ modulo $9$ would reduce to one modulo $3$, which is impossible. A Jacobi symbol of $1$ records a product of local signs; it does not assert that every local sign is positive, or that a quadratic congruence is soluble.

Factor $Q={\prod }_i{p}_i$ and $Q^{\prime }={\prod }_j{q}_j$, retaining repeated prime factors. If $P$ has a common prime factor with $Q{Q}^{\prime }$, it has one with at least one of $Q,Q^{\prime }$, and both sides of the desired equality are zero. Otherwise the definition of the Jacobi symbol givesAn empty product is $1$, so the argument includes either denominator being $1$.

For a prime number $p$, multiplicativity of the Legendre symbol says $(P{P}^{\prime }/p)=(P/p)(P^{\prime }/p)$, including the case of a zero factor. Therefore, writing $Q={\prod }_i{p}_i$ with repetitions,This product definition still agrees with the stipulated zero when the numerator and denominator are not coprime. For $Q=1$ all three symbols are $1$.

If $P\equiv P^{\prime }(\mathrm{mod}Q)$, then $P\equiv P^{\prime }(\mathrm{mod}p)$ for each prime factor $p$ of $Q$. The Legendre symbol depends only on the numerator's residue class, so the corresponding factors agree. Also $\gcd (P,Q)=\gcd (P^{\prime },Q)$, covering the zero cases. Multiplying givesThe convention for denominator $1$ gives the same conclusion there.

The supplementary law for the Legendre symbol is $(-1/p)=(-1{)}^{(p-1)/2}$ for odd prime numbers $p$. For odd integers $a,b$,and the last term is even. Induction over the prime factors of $Q$ therefore gives ${\sum }_i(p_i-1)/2\equiv (Q-1)/2(\mathrm{mod}2)$. ConsequentlyFor $Q=1$ the exponent is zero.

The second supplementary law for the Legendre symbol is $(2/p)=(-1{)}^{(p^2-1)/8}$. To multiply these signs, observe that for odd $a,b$,Both factors in the numerator are divisible by $8$, so the right side is even. Applying this identity repeatedly to the prime factorization givesAgain the convention at $Q=1$ agrees.

Write $P={\prod }_i{p}_i$, $Q={\prod }_j{q}_j$, counting repetitions. Since $P,Q$ are coprime, every pair $p_i,q_j$ consists of distinct odd prime numbers. Quadratic reciprocity for the Legendre symbol givesMultiplying over all $i,j$ and using multiplicativity of the Jacobi symbol yields the sign exponentby the odd-product parity identity proved in (b)(i). Thus the Jacobi reciprocity law isIf either integer is $1$, its factorization is empty and both sides equal $1$.

Complete the square to obtain the equivalent quadratic congruenceHere $\gcd (1111,8093)=1$: the Euclidean algorithm has successive nonzero remainders $316,163,153,10,3,1$. If this modular congruence had a solution, the Jacobi symbol $(1111/8093)$ would be $1$, since a square coprime to an odd modulus has Legendre symbol $1$ at every prime factor. Calculate instead, using Jacobi reciprocity and reduction of numerators,Therefore there is no solution. This obstruction does not require a separate primality test for $8093$; the Jacobi symbol suffices.