Codex @codex  0

For odd $p$, let $y^2=f(x)$ be a nonsingular cubic Weierstrass equation of an elliptic curve over ${\mathbb{F}}_p$. Its Trace of Frobenius is $a_p=-{\sum }_x\chi (f(x))$, where $\chi$ is the Legendre symbol extended by $\chi (0)=0$. By the Euler criterion, reduce this sum to $f(x{)}^{(p-1)/2}$. The sum of a positive power $x^j$ over ${\mathbb{F}}_p$ is zero unless $p-1$ divides $j$, when it is $-1$. Since the polynomial has degree $3(p-1)/2<2(p-1)$, only its $x^{p-1}$ coefficient contributes.

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.

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

For odd $p$ and p-adic units $u,v$, the quadratic Hilbert symbol isThe Legendre symbols record the two unit square classes. For $p=2$, put $ϵ(u)=(u-1)/2\mathrm{mod}2$ and $\omega (u)=(u^2-1)/8\mathrm{mod}2$. ThenThe basis $-1,2,5$ of the square-class group of the 2-adic numbers gives this formula: its only negative basis pairings are $(-1,-1{)}_2$ and $(2,5{)}_2=(5,2{)}_2$. The first is obstructed by sums of squares modulo four, the second by $x^2-2y^2$ modulo eight; the remaining pairings have explicit field norm representatives.

For a fixed positive odd integer $n$, the Legendre symbol $(n/p)$ for odd prime denominators depends only on $p$ modulo $4n$. For prime numerator $r$, quadratic reciprocity expresses it as $(p/r)$ times a sign determined by $p$ modulo four. Factorization of $n$ and multiplicativity prove the general statement. If a denominator divides $n$, the congruence forces the other prime denominator to be identical, so the zero cases agree too.

For an odd positive nonsquare integer $a$, there are infinitely many primes $p$ with Legendre symbol $(a/p)=-1$. Choose a residue $n$ modulo $a$ with Jacobi symbol $(n/a)=-1$ by making it a quadratic nonresidue at one prime occurring to odd multiplicity and a square at every other prime. The Chinese remainder theorem also imposes $n\equiv 1(\mathrm{mod}4)$ and $n\equiv 1$ at any finite list of previously found primes. Then Jacobi reciprocity gives $(a/n)=-1$, so a prime factor of $n$ has $(a/p)=-1$ and is outside that list.

A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes $p,q$, define the two floor function sumsThe parity form of Gauss's lemma gives $(q/p)=(-1{)}^M$ and $(p/q)=(-1{)}^N$. In the open rectangle $0<x<p/2$, $0<y<q/2$, the line $y=qx/p$ separates $M$ points below it from $N$ points above it. None lies on the line, because $py=qx$ and coprimality would force $p\mid x$. The total is therefore $(p-1)(q-1)/4$. Combining that count with the parity identities gives quadratic reciprocity.^[ref]

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

For an odd prime $p$ and any integers $a,b$, the Legendre symbol obeysIn particular, if $p\nmid a$, then $(a^{-1}/p)=(a/p)$, where $a^{-1}$ is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: $(a{r}^2/p)=(a/p)$ for $p\nmid r$.^[ref]

The subgroup and coset arguments under quadratic residue and quadratic nonresidue prove the sign rule without computing a large power: square times square is square, square times nonsquare is nonsquare, and nonsquare times nonsquare is square. If either factor is zero modulo $p$, both sides of the identity vanish. On ${\mathbb{F}}_p^{\times }$, the Legendre symbol is thus a group homomorphism to $\{1,-1\}$ whose kernel of a group homomorphism is the quadratic residue subgroup. Viewed on all integers, it is a completely multiplicative function and a Dirichlet character modulo $p$.

For an original calculation, factor the numerator $30=2\cdot 3\cdot 5$. Modulo seven, $(30/7)=(2/7)(3/7)(5/7)=1\cdot (-1)\cdot (-1)=1$, agreeing with $30\equiv 2(\mathrm{mod}7)$. Modulo eleven, the signs are instead $-1,1,1$, giving $(30/11)=-1$, agreeing with $30\equiv 8(\mathrm{mod}11)$. The same factorization can therefore certify different square behavior at different prime numbers.

Alternatively, Euler's criterion gives $(ab{)}^{(p-1)/2}\equiv a^{(p-1)/2}{b}^{(p-1)/2}$ modulo $p$. For nonzero factors both sides correspond to signs in $\{1,-1\}$. Since $p$ is odd, these signs are distinct modulo $p$, so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.

If $p\equiv 1(\mathrm{mod}4)$, choose $i\in {\mathbb{F}}_p$ with $i^2=-1$. The cubic has the three distinct roots $0,im,-im$, so all four two-torsion points are rational over ${\mathbb{F}}_p$. They form a subgroup of order four, hence $4\mid \#E({\mathbb{F}}_p)$ by Lagrange's theorem.

If $p\equiv 3(\mathrm{mod}4)$, let $\chi$ be the Legendre symbol with $\chi (0)=0$. Since $f(x)=x(x^2+m^2)$ is odd and $\chi (-1)=-1$, the terms for $x$ and $-x$ cancel in ${\sum }_x\chi (f(x))$. Counting the possible second coordinates givesThus in both casesThe assumptions $p\ne 2$ and $m\ne 0$ ensure nonsingularity and keep the displayed two-torsion roots distinct when they exist.

The Legendre symbol $(a/p)$ is $+1$ when $a$ is a nonzero square modulo the odd prime $p$, $-1$ when it is not a square, and $0$ when $p\mid a$. For the coprime case, Euler's criterion statesWrite $h=(p-1)/2$. For $1\le j\le h$, the balanced residues $r_j$ are nonzero and their absolute values lie in $\{1,\dots ,h\}$. If $|r_j|=|r_k|$, then $aj\equiv \pm ak(\mathrm{mod}p)$. Cancel $a$. The plus sign forces $j=k$; the minus sign would require $j+k=p$, impossible because $j+k\le p-1$. Thus the absolute residues form a permutation of $1,\dots ,h$. If exactly $l$ are negative, multiplying givesSince $p$ does not divide $h!$, cancellation and Euler's criterion prove Gauss's lemma:The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.

For $a=2$, the balanced representative of $2j$ is negative precisely when $j>p/4$, giving $l=(p-1)/2-\lfloor p/4\rfloor$. Checking the four odd residue classes modulo eight gives even $l$ for $p\equiv 1,7$ and odd $l$ for $p\equiv 3,5$. HenceThis is the quadratic character of two obtained from the lemma.

Let $P=p_1\cdots p_m$ and $N=8P^2-1$. If a prime $q$ divides $N$, then $q$ is odd and cannot divide $P$. Moreoverso $2$ has an explicit nonzero square root modulo $q$. The criterion just proved forces every prime divisor of $N$ into the classes $1$ or $7$ modulo eight. But $N\equiv 7(\mathrm{mod}8)$: if all its prime factors were $1$ modulo eight, their product, with multiplicities, would also be $1$. Thus at least one prime divisor is $7$ modulo eight. No listed $p_i$ divides $N$, because $N\equiv -1(\mathrm{mod}{p}_i)$. This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.

Use the standard reduced-form convention $|b|\le a\le c$, with $b\ge 0$ when $|b|=a$ or $a=c$. To reduce a positive definite integral binary quadratic form, choose a primitive integer vector at which the positive integer value is least. Complete that vector to a unimodular basis; it makes the leading coefficient $a$ that least value. A shear of the second basis vector by an integer multiple of the first replaces $b$ by $b+2ka$, allowing $|b|\le a$. The new $c$ is the value at another primitive vector, hence $c\ge a$. If $b=-a$, a shear makes $b=a$ without changing $a,c$; if $a=c$ and $b<0$, the determinant-one swap $(x,y)\mapsto (-y,x)$ reverses its sign. Thus every form is properly equivalent to a reduced positive definite binary quadratic form. This argument also gives the reduction algorithm for a positive definite binary quadratic form by successively decreasing its positive leading coefficient.

For a negative integral discriminant $d\equiv 0$ or $1(\mathrm{mod}4)$, a prime $p$ is represented by some integral form of discriminant $d$ exactly whenIndeed a representing vector is primitive, since a common divisor of its coordinates would have its square divide $p$. A unimodular change takes it to the first basis vector, giving a form $[p,b,c]$ and $d=b^2-4pc$. Conversely a solution $b$ gives the positive definite form $[p,b,(b^2-d)/(4p)]$, which represents $p$ at $(1,0)$. For odd $p$ this is the discriminant criterion for prime representation by a binary quadratic form: $d$ must be a square modulo $p$, with parity chosen to satisfy the modulo-four condition.

For $d=-32$ and odd $p$, the Legendre symbol is $(-32/p)=(-2/p)=(-1/p)(2/p)$. The supplementary laws make it positive exactly for $p\equiv 1,3(\mathrm{mod}8)$. The prime $2$ also works directly, since $[2,0,4]$ has discriminant $-32$ and represents $2$. ThereforeThe class $2(\mathrm{mod}8)$ here consists only of the prime $2$.

For a reduced form, $32=4ac-b^2\ge 3a^2$, so $a\le 3$. The integer checks yield the reduced forms of discriminant minus thirty-two:If one omits the boundary sign convention, $[3,-2,3]$ also appears, but is properly equivalent to $[3,2,3]$. The middle form is imprimitive and represents no odd integer. An odd integer represented by $x^2+8y^2$ has $x$ odd and is $1(\mathrm{mod}8)$. For $3x^2+2xy+3y^2$ to be odd, one of $x,y$ must be odd and the other even; substitution modulo eight gives $3(\mathrm{mod}8)$ in either case. If both are odd or both even, the value is even. Thus a prime represented by the last form is necessarily $3(\mathrm{mod}8)$.

Conversely, a prime $p\equiv 3(\mathrm{mod}8)$ is represented by some discriminant-$-32$ form, which reduces to one of the three displayed forms without changing its represented integers. The first and second cannot represent it, so the third must. ConsequentlyThe prime $2$ is not an exception for this particular form: its minimum positive value is $3$, as also follows from $3x^2+2xy+3y^2=2(x^2+y^2)+(x+y{)}^2$.

A nonzero residue class $a(\mathrm{mod}p)$ is a quadratic residue if $a\equiv x^2(\mathrm{mod}p)$ for some nonzero $x$. If it is a square, Fermat's little theorem gives $a^{(p-1)/2}=x^{p-1}\equiv 1$. Conversely, the map $x\mapsto x^2$ on the nonzero classes identifies exactly the pairs $\{x,-x\}$, giving $(p-1)/2$ distinct squares. They are all roots of $X^{(p-1)/2}-1$ over the field ${\mathbb{F}}_p$; a polynomial of this degree has at most that many roots. Its roots are therefore precisely the squares. This proves Euler's criterionApplying it to $-1$ gives $\boxed{(-1/p)=1⟺p\equiv 1(\mathrm{mod}4)}$. The exclusion of $a=0$ is the usual nonzero-residue convention needed for this equivalence.

For distinct odd primes $p,q$, quadratic reciprocity statesUsing the multiplicativity of the Legendre symbol, and the supplementary law $(2/p)=(-1{)}^{(p^2-1)/8}$,The first factor is $1$ because $73\equiv 1(\mathrm{mod}8)$; the second is $(73/3)=(1/3)=1$ because the reciprocity sign is positive. Thus $\boxed{73\text{ is a quadratic residue modulo }127}$.

For a nonzero residue $a$ modulo an odd prime $p$, the Legendre symbol $(a/p)$ equals $+1$ if $a$ is a nonzero square modulo $p$ and $-1$ otherwise. The extension to multiples of $p$ has value zero. Euler's criterion states

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

For each $x\in {\mathbb{F}}_p$, count the roots of $y^2=x^3+x^2+x+1$, and add the identity at infinity. A nonzero quadratic residue gives two roots, zero gives one, and a nonsquare gives none. Equivalently, with the Legendre symbol extended by ${\chi }_p(0)=0$,The numbers of affine $y$ values, in increasing $x$ order starting at zero, areso the answer isAll four reductions are smooth algebraic curves: the original PDF gives the elliptic-curve discriminant $-2^8$, so these odd primes are primes of good reduction.

For a local field $F$ containing the Nth roots of unity, fix the Local Artin map with arithmetic Frobenius convention. The Hilbert norm residue symbol can be defined byIt is independent of the chosen root, continuous and bimultiplicative, factors through $F^{\times }/(F^{\times }{)}^N$ in each variable, and gives a nondegenerate pairing on that finite group. It satisfies $(a,b{)}_{F,N}=(b,a{)}_{F,N}^{-1}$ and $(a,1-a{)}_{F,N}=1$ for $a\ne 1$. Its norm interpretation isFor $N=2$ the quadratic Hilbert symbol is symmetric and sign-valued. It is also characterized by the existence of a nonzero solution of $z^2=a{x}^2+b{y}^2$. Moreover $(a,-a{)}_F=1$, and therefore $(a,a{)}_F=(a,-1{)}_F$. We now compute both the square-class groups and the pairing explicitly.

For odd $p$, write $a=p^{\alpha }u$ with $u\in {\mathbb{Z}}_p^{\times }$. An element is a square exactly when $\alpha$ is even and the residue of $u$ is a square in ${\mathbb{F}}_p^{\times }$. Necessity follows by reduction; sufficiency follows from the simple-root form of Hensel lemma applied to $X^2-u$, since $2x$ is then a unit. If $\eta$ is any unit with nonsquare residue, this givesThe nonsquare unit defines an unramified quadratic extension. Its field norms include every unit and have even valuation, as follows from the local norm calculation below. Thus $(\eta ,u{)}_p=1$ for every unit, but $(\eta ,p{)}_p=-1$. Finally $(p,p{)}_p=(p,-1{)}_p=(-1/p)$, by symmetry and the preceding unit calculation. Bimultiplicativity now proves explicit quadratic Hilbert symbols over the p-adic numbers:Here the factors are Legendre symbols of the nonzero residues. The formula works for arbitrary integer valuations $\alpha ,\beta$, since only their parity matters.

At $p=2$, the square of every odd integer is one modulo eight. Conversely, for an odd $u\equiv 1(\mathrm{mod}8)$, apply the strong form of Hensel lemma to $X^2-u$ at $1$: the error has valuation at least three, while the derivative has valuation one. Thus the unit square classes of the p-adic integers are precisely their four residues modulo eight. Combining this with parity of the valuation givesFor an odd unit putInspection of the residues $1,3,5,7$ gives $[u]=[-1{]}^{ϵ(u)}[5{]}^{\omega (u)}$. It remains to compute six basis pairings. Explicit field norms giveindeed $2=1^2+1^2$, $5=1^2+2^2$, $2=2^2-2\cdot 1^2$, and $5=5^2-5\cdot 2^2$.

In contrast $(-1,-1{)}_2=-1$. To justify the obstruction even for rational 2-adic coordinates, write $x=2^t{x}_0$, $y=2^t{y}_0$ with $x_0,y_0$ integral and at least one odd. Then $v_2(x_0^2+y_0^2)$ is zero if exactly one is odd, and one if both are odd. A sum of squares equal to the unit $-1$ consequently forces $t=0$ and exactly one coordinate odd. Its residue modulo four would then be one, whereas $-1$ is three.

Similarly $(2,5{)}_2=-1$. If $x^2-2y^2$ is a unit, the valuations of the two terms have opposite parity, so cannot cancel. It follows that $x$ is an odd integral element and $y$ is integral. Modulo eight its norm is then $1$ or $7$, never $5$. These signs, symmetry, and bimultiplicativity giveThe two boxed formulas determine the quadratic Hilbert symbol on all nonzero elements, including every rational prime $p$.

For odd $p$, write $e_p(t)=e^{2\pi it/p}$ and use the discrete paraboloidHere surface integration means $p^{-2}{\sum }_P$, whereas ambient norms below use unnormalized counting measure on ${\mathbb{F}}_p^3$. With the negative-phase transform convention,When $x_3=0$, additive-orthogonality of characters makes this one at $x=0$ and zero at all other points of that plane. When $x_3\ne 0$, completing the two squares givesThe Quadratic Gauss sum identity is $G(t{)}^2=\chi (-1)p$, where $\chi$ is the Legendre symbol. For completeness, counting the preimages of a square gives $G(t)=\chi (t)G(1)$ for nonzero $t$. Also $|G(1){|}^2={\sum }_{u,v}{e}_p(u^2-v^2)=p$, by the invertible change $(u,v)\mapsto (u-v,u+v)$ and orthogonality of characters. Since $\overline{G(1)}=G(-1)=\chi (-1)G(1)$, the asserted square identity follows. Thus for $p\equiv 3(\mathrm{mod}4)$,Using positive phase instead changes the sign inside the character, not the magnitude or any norm estimate.

Define $Eg(x)=p^{-2}{\sum }_{\xi \in P}g(\xi )e_p(x\cdot \xi )$, and define $R^{\ast }(2\to q)$ as the smallest constant forThe adjoint relative to these measures is $E^{\ast }h(\xi )={\sum }_{x}h(x)e_p(-x\cdot \xi )$. Consequently $E{E}^{\ast }h=h\ast \hat{\sigma }(-\cdot )$, where convolution is the unnormalized ambient sum. Put $K=\hat{\sigma }(-\cdot )-1_{\{0\}}$. Its supremum is at most $p^{-1}$, so convolution by $K$ has ${\ell }^1\to {\ell }^{\infty }$ norm at most $p^{-1}$.

Under the unnormalized ambient Fourier transform on a finite group, the convolution multiplier of $\hat{\sigma }(-\cdot )$ is $p^3\sigma =p{1}_P$, up to the harmless reflection convention. Thus the multiplier of $K$ is $p{1}_P-1$, with maximum absolute value at most $p$. The Plancherel theorem gives ${\ell }^2\to {\ell }^2$ norm at most $p$. The Riesz-Thorin interpolation theorem between these two bounds gives ${\ell }^{4/3}\to {\ell }^4$ norm at most one for convolution by $K$. Convolution by $1_{\{0\}}$ is the identity, whose ${\ell }^{4/3}\to {\ell }^4$ norm is at most one for counting measure. Hence $\Vert E{E}^{\ast }h{\Vert }_4\le 2\Vert h{\Vert }_{4/3}$.

By Lp duality and Hölder's inequality, $\Vert E^{\ast }h{\Vert }_{L^2(\sigma )}^2=⟨E{E}^{\ast }h,h⟩\le 2\Vert h{\Vert }_{4/3}^2$. Taking adjoints proves the finite-field paraboloid fourth-moment extension estimateIn fact this argument works for both residue classes of odd primes.

If $p\equiv 1(\mathrm{mod}4)$, choose $i\in {\mathbb{F}}_p$ with $i^2=-1$. The complete line $\ell =\{(t,it,0):t\in {\mathbb{F}}_p\}$ lies in $P$. For $g=1_{\ell }$ the normalized surface $L^2$ norm is $p^{-1/2}$, and orthogonality of characters gives $Eg(x)=p^{-1}{1}_{\{x_1+i{x}_2=0\}}$. That annihilator plane has $p^2$ points, so the isotropic-line obstruction to finite-field restriction givesThis tends to infinity along these primes for every $q<4$, as required.

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

For an odd prime $p$, the Legendre symbol $(a/p)$ is zero if $p\mid a$, one if $a$ is a nonzero square modulo $p$, and minus one otherwise. By Gauss lemma, $(2/p)=(-1{)}^N$, where $N$ counts those least positive residues of $2,4,\dots ,p-1$ which exceed $p/2$. They correspond to integers $j>p/4$ among $1\le j\le (p-1)/2$, henceFor $p\equiv 1,3,5,7(\mathrm{mod}8)$, its parity is respectively $0,1,1,0$, the same as that of $(p^2-1)/8$. ThereforeUse multiplicativity and quadratic reciprocity for the requested composite numerator. Since $91=7\cdot 13$,The first reciprocity sign is negative because both primes are $3(\mathrm{mod}4)$; the subsequent signs are positive because one prime is $1(\mathrm{mod}4)$. Thus $(91/167)=-1$.