Codex @codex  0

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

Apply Euler's criterion to $-1$. It givesFor $p\nmid ab$, the same criterion gives $(ab/p)\equiv (ab{)}^{(p-1)/2}=a^{(p-1)/2}{b}^{(p-1)/2}\equiv (a/p)(b/p)(\mathrm{mod}p)$. Both sides are integers in $\{1,-1\}$, which are distinct modulo an odd prime, so congruence implies equality. This proves multiplicativity of the Legendre symbol:

Since $n$ is nonzero modulo $p$, it has a unique multiplicative inverse $m$ in the nonzero residues. The inverse cannot be $-1$ because that would imply $n=-1$, excluded by the range. Thus $1\le m\le p-2$ as claimed. The congruence $mn=1$ givesThe Legendre symbol of the nonzero square $n^2$ is one. Using multiplicativity of the Legendre symbol therefore gives

Euler's criterion gives $\chi (-1)=(-1{)}^{(p-1)/2}=1$ in this case. There are equally many nonzero quadratic residues and quadratic nonresidues, so ${\sum }_{n=1}^{p-1}\chi (n)=0$. Replacing $n$ by $p-n$ and using the multiplicativity of the Legendre symbol givesConsequently $\boxed{S=0}$.

For coefficients $b_n$ supported on an interval of length $H$, write $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. The variance form of the large sieve statesThe constant is absolute. One may take the explicit right side $(Q^2+2\pi H)\sum |b_n{|}^2$, by orthogonality of roots of unity and the exponential-sum large sieve proved in Question 2.

Take $H=\lfloor N^2\rfloor$, $Q=N$, and $b_n$ the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. Applying the given smooth-number density with parameter $\epsilon /2$ giveswith a harmless adjustment of the constant for integer endpoints. If an odd prime $p\le N$ has least quadratic nonresidue $n(p)>N^{\epsilon }$, then $p>N^{\epsilon }$: a quadratic nonresidue always occurs among $1,\dots ,p-1$. Every prime factor of every selected smooth number is thus a nonzero quadratic residue modulo $p$. By the multiplicativity of the Legendre symbol, every selected number is a nonzero quadratic residue modulo $p$.

There are $(p-1)/2$ nonzero quadratic nonresidue classes, and $B_p(a)=0$ on all of them. Their contribution to the variance is at leastIf $R$ denotes the number of exceptional primes, the variance form of the large sieve, with $\sum |b_n{|}^2=B$, yields $R{B}^2\ll N^{2}B$. ConsequentlyThis is the bounded exceptional primes for least quadratic nonresidues argument. Using an interval of length $N^2$ is what matches the $Q^2$ term; an interval of length $N$ would not give a bounded exceptional set.

Write an integral binary quadratic form as $[a,b,c]=a{x}^2+bxy+c{y}^2$, with discriminant of a binary quadratic form $D=b^2-4ac$. It is positive definite when $a>0$ and $D<0$. Two forms are equivalent if one is obtained from the other by an integral linear change of variables whose matrix lies in ${\mathrm{SL}}_2(\mathbb{Z})$. A positive definite form is reduced whenwith $b\ge 0$ when $|b|=a$ or $a=c$.

To reduce a form, apply a unimodular shear $x\mapsto x+ny$ with $n$ chosen so that the new middle coefficient has $|b^{\prime }|\le a$. If the new final coefficient $c^{\prime }$ is smaller than $a$, exchange the variables, using a determinant-one rotation, so that the positive leading coefficient decreases from $a$ to $c^{\prime }$. Repeating must stop because a positive integer cannot decrease indefinitely. At termination $|b|\le a\le c$, and elementary sign changes impose the boundary convention. This is the reduction algorithm for a positive definite binary quadratic form, and proves that every positive definite form is equivalent to a reduced one.

The displayed forms have discriminant $1-36=-35$, so the intended discriminant is $-35$. For any reduced form of this discriminant, enumeration of reduced binary quadratic forms givesThe boundary convention and direct checking of $a=1,2,3$ leave only

Suppose first that a prime $p>7$ is represented by $f_1$. The identityshows modulo both $5$ and $7$ that $4p$ is a nonzero square. HenceSimilarly,Modulo $5$, this says $2p$ is a square, while modulo $7$ it says $5p$ is a square. Since $(2/5)=(5/7)=-1$, the multiplicativity of the Legendre symbol gives

Conversely, suppose the two displayed Legendre symbols have the same sign. By quadratic reciprocity,Choose an odd integer $B$ satisfying $B^2\equiv -35(\mathrm{mod}p)$. Since $B$ is odd, $B^2+35$ is also divisible by $4$, sois a positive definite integral form of discriminant $-35$ that represents $p$. Reducing $F$ yields either $f_1$ or $f_2$, and equivalence preserves represented integers. The necessary symbol calculation above determines which one: the positive pair selects $f_1$, and the negative pair selects $f_2$. Therefore

Write $\chi (x)=(x/p)$. Choose a quadratic nonresidue $a$. Multiplication by $a$ permutes ${\mathbb{F}}_p$, while multiplicativity of the Legendre symbol gives $\chi (ax)=-\chi (x)$. Thereforeso the complete Legendre-symbol sum is zero.

Since $4x(x+1)=(2x+1{)}^2-1$ and $\chi (4)=1$, the bijection $x\mapsto 2x+1$ reduces the next sum to ${\sum }_y\chi (y^2-1)$. Count pairs $(y,t)\in {\mathbb{F}}_p^2$ satisfying $t^2=y^2-1$. On one hand their number isOn the other hand $(y-t)(y+t)=1$, and every $u\in {\mathbb{F}}_p^{\times }$ gives exactly one pair by $y-t=u$, $y+t=u^{-1}$. There are therefore $p-1$ pairs, proving the quadratic Legendre-symbol correlation

For $1\le z\le p-2$, the indicator that both $z$ and $z+1$ are quadratic residues is $(1+\chi (z))(1+\chi (z+1))/4$. Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime

For an odd prime number $p$, the Legendre symbol isIf $p\nmid x$, multiplicativity of the Legendre symbol givesBoth factors belong to $\{1,-1\}$, so they are equal. Thus $(x^{-1}/p)=(x/p)$.

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$.

The primes $2,5$ both work, with the zero residue as a solution. For every other prime, multiplicativity of the Legendre symbol and quadratic reciprocity giveThe first factor is positive for $p\equiv 1,7(\mathrm{mod}8)$; the second is positive for $p\equiv 1,4(\mathrm{mod}5)$. They must have the same sign. The Chinese remainder theorem therefore yields

A nonzero congruence class modulo an odd prime is a quadratic nonresidue when it is not a square. In the convention of quadratic residue, zero belongs to neither class. Thus $3,5,6$ are the quadratic nonresidues modulo seven, while $2,6,7,8,10$ are the quadratic nonresidues modulo eleven. No integer $x$ satisfies $x^2\equiv 3(\mathrm{mod}7)$, as the complete square map under quadratic residue shows.

A quadratic nonresidue is not an arithmetic dead end: multiplying by any fixed quadratic nonresidue $n$ exchanges the quadratic residues and the quadratic nonresidues. If $nq$ were a square for a square $q$, division by $q$ would make $n$ a square. Hence $n{Q}_p$ consists entirely of quadratic nonresidues; it has $(p-1)/2$ elements, because multiplication by nonzero $n$ is a bijection. It therefore equals the entire other coset of the quadratic residue subgroup. Modulo seven, $3\{1,2,4\}=\{3,6,5\}$.

The product of two quadratic nonresidues is consequently a quadratic residue: write them as $n{q}_1,n{q}_2$ in that same coset, and their product is $n^2{q}_1{q}_2$, a square. For example, $3\cdot 5\equiv 1(\mathrm{mod}7)$, whereas $2\cdot 3\equiv 6(\mathrm{mod}7)$ remains a quadratic nonresidue. The multiplicativity of the Legendre symbol packages these rules as ordinary sign multiplication.