Complete Legendre-symbol sum Created 2026-09-29 Updated 2026-11-05
For an odd prime , the complete sum of the Legendre symbol is
Choose a quadratic nonresidue . Multiplication by permutes the finite field , while multiplicativity of the Legendre symbol gives . The sum is therefore equal to its own negative, and is zero. Equivalently, among the nonzero residue classes, exactly half are quadratic residues and half are quadratic nonresidues; the zero term contributes zero.
Let be an odd prime and let be integers with . The quadratic congruence
has a solution exactly when its discriminant is zero or a quadratic residue modulo .
Indeed, completing the square gives the equivalent equation
Multiplication by and translation by give a bijection of the residue classes, because is invertible modulo . Each square root of therefore gives exactly one solution .
Consequently the number of distinct solutions is , using the Legendre symbol: one for zero discriminant, two for a nonzero quadratic residue, and none for a quadratic nonresidue. The hypotheses matter: if the equation can become linear, while at division by is unavailable.
Euler's criterion Created 2026-09-24 Updated 2026-10-18
For an odd prime and , 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 if a nonnegative remainder is used. The formula also holds when , because and both sides are zero modulo .[ref]
For example, modulo seven the exponent is three: confirms that two is a quadratic residue, while confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots of .
A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put . If in the prime field, then . There are already such quadratic residues. The nonzero polynomial has polynomial degree , so it has no other polynomial roots. Finally, for every nonzero , Fermat's little theorem gives . Factoring in the field shows ; every quadratic nonresidue must take the remaining value . 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 . Exponentiation by squaring computes the required power without listing fifty squares:
Therefore and has no solution. Each intermediate product is reduced modulo , 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, , which is neither one nor minus one. Although four is a nonzero square modulo nine, , 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.
Existence of an Euler witness for every odd composite integer Created 2026-09-29 Updated 2026-11-05
Every composite number that is an odd integer has an Euler witness. There are two cases.
If divides for a prime number , write with and . The Chinese remainder theorem chooses and . This base is a unit modulo and has Jacobi symbol , because it is one modulo every prime divisor. But with , the binomial theorem gives . Since , this is not one, so the Euler congruence fails.
If is squarefree, it has at least two distinct prime factors. Choose to be a quadratic nonresidue modulo one factor and one modulo every other factor, again by the Chinese remainder theorem. Then , while is one modulo a different prime factor. It therefore cannot equal the Jacobi symbol modulo .
Gauss's lemma (number theory) Created 2026-10-14 Updated 2026-11-05
Let be an odd prime and an integer with . Reduce
to their least positive residue classes modulo . If exactly of these representatives exceed , Gauss's lemma states
The symbol on the left is the Legendre symbol. For example, and give representatives . Exactly one exceeds , so is a quadratic nonresidue modulo .
For a proof, replace every representative above by its negative modulo , obtaining numbers in . These numbers are distinct: equality would give , forcing because . They therefore form a permutation of . Multiplying the signed representatives gives
The factorial is invertible modulo . Cancelling it and applying the Euler criterion proves the lemma. Counting signs can thus replace a potentially large modular exponentiation.
Infinitely many prime quadratic nonresidues of a nonsquare integer Created 2026-10-14 Updated 2026-11-05
For an odd positive nonsquare integer , there are infinitely many primes with Legendre symbol . Choose a residue modulo with Jacobi symbol 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 and at any finite list of previously found primes. Then Jacobi reciprocity gives , so a prime factor of has and is outside that list.
Least quadratic nonresidue Created 2026-10-06 Updated 2026-11-05
For an odd prime , the least quadratic nonresidue is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo . For example, the nonzero quadratic residues modulo seven are , so .
The least quadratic nonresidue is itself a prime number. Otherwise it has a factorization with . By minimality, both residue classes are quadratic residues, so and would give , a contradiction. This illustrates why multiplicative information can constrain a least exceptional integer.
Legendre symbol Created 2026-09-24 Updated 2026-10-18
For an integer and an odd prime , the Legendre symbol is the integer valued function
Its value depends only on the congruence class of modulo ; the displayed notation is a symbol, not division. The value zero handles separately from quadratic residues and quadratic nonresidues.[ref]
For example, , , , and . The equality 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 in the prime field ,
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 a prime number , let be the sum of the least positive quadratic residues below . Then
For example, at the relevant quadratic residues are , and their sum is .
To prove the identity, put , let be the sum of all least positive nonzero quadratic residues, and let count those above . The second supplementary law for quadratic reciprocity gives , so doubling permutes these residue classes. Reducing each doubled representative modulo subtracts exactly times. Hence , or .
Since , the first supplementary law for quadratic reciprocity says is a quadratic nonresidue. Exactly one of is therefore a quadratic residue for each . The lower-half choices sum to ; the upper-half choices sum to . Consequently
Substituting gives . Both congruence conditions have a role: one makes doubling a permutation, and the other makes each opposite pair contain exactly one quadratic residue.
Multiplicativity of the Legendre symbol Created 2026-09-29 Updated 2026-10-18
For an odd prime and any integers , the Legendre symbol obeys
In particular, if , then , where is a modular multiplicative inverse. Multiplication by a nonzero square also leaves the Legendre symbol unchanged: for .[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 , both sides of the identity vanish. On , the Legendre symbol is thus a group homomorphism to 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 .
Figure 1.
Products modulo seven: the Legendre symbol reduces a six-by-six table to sign multiplication
. Rows and columns put quadratic residues before quadratic nonresidues . Every cell displays the product modulo seven and its Legendre symbol. The four blocks have signs , showing the subgroup and its other coset. Details.
For an original calculation, factor the numerator . Modulo seven, , agreeing with . Modulo eleven, the signs are instead , giving , agreeing with . The same factorization can therefore certify different square behavior at different prime numbers.
Alternatively, Euler's criterion gives modulo . For nonzero factors both sides correspond to signs in . Since is odd, these signs are distinct modulo , so the modular congruence proves the asserted equality of integers, not merely an equality of representatives.
For positive odd coprime integers , the Jacobi reciprocity law is
Factor . Since is not a square, some is odd. Choose a quadratic nonresidue modulo that , and choose residue one modulo each other . The Chinese remainder theorem provides a positive with these residues and with . Multiplicativity of the Jacobi symbol then gives .
Suppose only finitely many primes satisfy . They are coprime to . Repeat the preceding Chinese remainder theorem construction, additionally imposing at every odd and taking to avoid two. Since , Jacobi reciprocity gives . Factoring this Jacobi symbol over the prime factors of shows that at least one such prime has . But none of the listed primes divides , a contradiction. This proves the infinitely many prime quadratic nonresidues of a nonsquare integer assertion.
Euler's criterion gives in this case. There are equally many nonzero quadratic residues and quadratic nonresidues, so . Replacing by and using the multiplicativity of the Legendre symbol gives
Consequently .
Factor . Since it is not a square, one exponent, say , is odd. Choose a nonzero quadratic nonresidue modulo ; one exists because the squaring map on the nonzero residues is two-to-one and hence has only images. The Chinese remainder theorem supplies a positive odd integer satisfying
Then and . The Jacobi reciprocity law proved in part (i), together with , gives . Factoring gives
All are odd and none divides . At least one factor must be negative, yielding an odd prime number . No theorem about primes in arithmetic progressions is needed.
Suppose is a quadratic nonresidue. On the nonzero residue classes modulo , define the involution
It is an involution because . A fixed point would satisfy , which is excluded by the quadratic nonresidue hypothesis. Thus it partitions the classes into disjoint pairs , each with product . Consequently
Now evaluate the same product by pairing every class with its own modular inverse. The only classes equal to their modular inverses solve and hence are and . All other pairs have product one. The complete product is therefore , so
Together with the preceding part, this is Euler's criterion; the pairing argument establishes the converse without assuming it.
For coefficients supported on an interval of length , write and . The variance form of the large sieve states
The constant is absolute. One may take the explicit right side , by orthogonality of roots of unity and the exponential-sum large sieve proved in Question 2.
Take , , and the indicator function of the -smooth numbers up to . Applying the given smooth-number density with parameter gives
with a harmless adjustment of the constant for integer endpoints. If an odd prime has least quadratic nonresidue , then : a quadratic nonresidue always occurs among . Every prime factor of every selected smooth number is thus a nonzero quadratic residue modulo . By the multiplicativity of the Legendre symbol, every selected number is a nonzero quadratic residue modulo .
There are nonzero quadratic nonresidue classes, and on all of them. Their contribution to the variance is at least
If denotes the number of exceptional primes, the variance form of the large sieve, with , yields . Consequently
This is the bounded exceptional primes for least quadratic nonresidues argument. Using an interval of length is what matches the term; an interval of length would not give a bounded exceptional set.
True. Since is not a square, some exponent is odd. Choose a quadratic nonresidue modulo that and choose residue one at every other prime. The Chinese remainder theorem produces a unit modulo with . Multiplication by permutes the residue classes modulo . Thus, by multiplicativity of the Jacobi symbol,
The sum is therefore . Nonunits contribute zero, so the permutation argument covers every term.
True. First suppose with maximal. By the Chinese remainder theorem, choose and modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For , the binomial theorem gives
because and all higher terms contain . It is therefore a witness to the desired failure.
If is square-free and composite, it has at least two prime factors. Choose to be a quadratic nonresidue at one prime and one at every other prime, again using the Chinese remainder theorem. Then . At a different odd prime , however, . These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.
If , square-freeness gives the cuspidal reduction . Its nonsingular group is isomorphic to the additive group , so it is cyclic of order .
Suppose . The reduction is an elliptic curve. Since , is a quadratic nonresidue. Pairing with in the quadratic-character sum and using
shows that the two contributions cancel. Therefore . The three roots are distinct, so the full 2-torsion is rational. A cyclic group has at most two elements killed by , hence is noncyclic. Thus
If the positive odd integer has prime factorization
its Jacobi symbol is
where each factor is a Legendre symbol; by convention . Thus the symbol is zero exactly when .
The quadratic reciprocity law for the Jacobi symbol says that for coprime positive odd integers ,
To prove it, write and . The quadratic reciprocity law for distinct odd primes states
Multiplying this identity over with multiplicities gives the required product of Jacobi symbols. Its sign exponent modulo two is
because multiplication of odd integers adds the quantities modulo two. This proves the law.
For the requested value, two applications of reciprocity give
since , , and is a quadratic nonresidue modulo .
Write . Choose a quadratic nonresidue . Multiplication by permutes , while multiplicativity of the Legendre symbol gives . Therefore
so the complete Legendre-symbol sum is zero.
Since and , the bijection reduces the next sum to . Count pairs satisfying . On one hand their number is
On the other hand , and every gives exactly one pair by , . There are therefore pairs, proving the quadratic Legendre-symbol correlation
For , the indicator that both and are quadratic residues is . Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime