For an odd prime , a nonzero congruence class is a quadratic residue when for some integer . Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.[ref]
Modulo seven, squaring the six nonzero congruence classes gives
Thus the set of quadratic residues is , and the quadratic nonresidues are . In particular, has exactly the two solutions : and . Modulo eleven the quadratic residues are instead . Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.
Figure 1.
The square map modulo seven and eleven: two inputs in every nonzero square fiber
. Each pair maps to one quadratic residue. The six nonzero inputs modulo seven give three outputs; the ten modulo eleven give five. The zero fiber is the single input zero, and each quadratic nonresidue has an empty fiber. Details.
Why do the square roots come in pairs? If , the prime number divides , so it divides one factor: or . For nonzero these are distinct, because is an odd prime. Every nonempty nonzero fiber of a function of therefore contains exactly two inputs. Pairing the nonzero congruence classes gives exactly quadratic residues and quadratic nonresidues. Including zero gives different squares, with one rather than two square roots for zero.
The quadratic residues form a subgroup of the multiplicative group of a finite field , with index of a subgroup two. Indeed, one is a square, , and ; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism and image of a function . The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.
This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence still makes sense, but the two-root count and the prime field argument need not survive. For example, has four solutions ; the Chinese remainder theorem separates the sign choices modulo three and five.
The quadratic congruence is soluble exactly when or . At , take .
For an odd prime , any solution is nonzero modulo . Fermat's little theorem gives
so is even and . Conversely, put when . Pairing opposite factors in the factorial gives
Wilson's theorem therefore gives , constructing a solution. For example, at the construction gives and . The criterion is the first supplementary law for quadratic reciprocity expressed as existence of a square root.
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 are the quadratic nonresidues modulo seven, while are the quadratic nonresidues modulo eleven. No integer satisfies , as the complete square map under quadratic residue shows.
A quadratic nonresidue is not an arithmetic dead end: multiplying by any fixed quadratic nonresidue exchanges the quadratic residues and the quadratic nonresidues. If were a square for a square , division by would make a square. Hence consists entirely of quadratic nonresidues; it has elements, because multiplication by nonzero is a bijection. It therefore equals the entire other coset of the quadratic residue subgroup. Modulo seven, .
The product of two quadratic nonresidues is consequently a quadratic residue: write them as in that same coset, and their product is , a square. For example, , whereas remains a quadratic nonresidue. The multiplicativity of the Legendre symbol packages these rules as ordinary sign multiplication.
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.
On a dyadic interval , every such exceptional prime makes all -smooth integers quadratic residues. By positive density of power-smooth integers, there are of these integers up to . Apply the variance form of the large sieve or its forbidden-residue consequence with interval length and prime cutoff . Each exceptional prime excludes residue classes and contributes at least a fixed positive amount to the sieve denominator. Hence each dyadic interval contains exceptional primes. Summing the intervals gives the logarithmic bound.
// Target: analytic-number-theory.bigb
If, for every , the smooth numbers up to with all prime factors at most have density at least , then for fixed there are only primes with . Apply the variance form of the large sieve to the indicator function of the -smooth numbers up to . For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times times that count. The density assumption with finishes the argument.
For an odd prime , put and let be the Legendre symbol. The quadratic Gauss sum is
With this choice of and the positive real square root of , its exact value is
The modulus can be established without determining the sign. Expanding and putting gives
The inner sum is for and otherwise, while because the nonzero quadratic residues and quadratic nonresidues are equally numerous. Also, complex conjugation followed by gives . Hence the sum is real for and purely imaginary for . These two observations determine its magnitude and its real or imaginary axis; choosing the sign in the exact evaluation is an additional step.
If and are the nonzero square and nonsquare classes modulo eleven and , then
Their sum is , and their difference is the quadratic Gauss sum .
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 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 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.
For every odd prime , the Legendre symbol correlation satisfies
The small negative value measures an exact dependence between neighboring square tests; it is not obtained by treating them as independent.
Count the pairs satisfying . For each , their number is : it is one for zero, two for a nonzero quadratic residue and zero for a quadratic nonresidue. The total is therefore plus the desired sum.
Set and . Since is invertible in this finite field, this is a bijection onto the solutions of
Choose any . Then , uniquely determining and . There are exactly choices of . Hence , proving the correlation identity.
For an odd prime , the number of integers such that both and are quadratic residues modulo is
For example, modulo the quadratic residues are . The qualifying pairs are and , giving .
Write for the Legendre symbol. On the specified range neither input is zero, so the indicator of the required event is . Expand and sum. The complete Legendre-symbol sum gives
The quadratic Legendre-symbol correlation gives : extending to the full finite field only adds the zero terms at . Thus the count is . The first supplementary law for quadratic reciprocity identifies and completes the formula.
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.
There are infinitely many prime numbers congruent to five modulo eight. Suppose instead that they form a finite list , and put , with if the list is empty. Then is an odd number and
For every prime factor of , the integer is nonzero modulo and . Thus a square root of minus one modulo a prime exists for , which forces . All prime factors are therefore one or five modulo eight. Their product is five modulo eight, so at least one prime factor is five modulo eight. Yet none of the divides , since . This contradicts completeness of the list.
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.
For an odd prime ,
For , write using a primitive root ; then the left side is , which is one exactly when is even and is a square.
For an odd prime , the Legendre symbol satisfies
Consequently, is a quadratic residue modulo exactly when .
By Euler's criterion, the Legendre symbol is congruent modulo to . Both sides are either or , and these are distinct modulo an odd prime, so the congruence gives equality. Finally, is even precisely for . For example, , whereas no square is modulo .
For every odd prime , the Legendre symbol of is
Thus is a quadratic residue for and a quadratic nonresidue for .
Apply Gauss's lemma to the representatives . With , exactly
exceed . For the four possible odd residues of modulo , this count has the same parity as . The lemma gives the formula. For example, at the representatives have two entries above , giving ; indeed .
Suppose that listed all prime numbers congruent to seven modulo eight. Put , with the empty product equal to one, and define
If an odd prime divides , then , so the second supplementary law for quadratic reciprocity forces or . Since is seven modulo eight, at least one of its prime factors is seven modulo eight. But for every listed prime, so this prime factor is new. The contradiction proves infinitude.
Let count primes at most congruent to modulo eight. Bounding the prime-power divisibility of
above and its size below gives, for all sufficiently large ,
For an integer matrix and prime , the commuting-matrix binomial theorem and divisibility of for give
For an odd prime , put
Then if , and for every .
For the first statement, the first supplementary law for quadratic reciprocity gives , where is the Legendre symbol. Pairing with gives
The same pairing in the complete Legendre-symbol sum shows that this half sum is zero, proving the exact equality.
For the second statement, multiplication by permutes the nonzero residue classes modulo . Reducing the weighted sum modulo and using multiplicativity of the Legendre symbol therefore gives . The coefficient is either or , and hence is invertible for . Thus . The restriction is necessary: at , .
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.
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.

Ancestors (4)

  1. Number theory
  2. Area of mathematics
  3. Mathematics
  4. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)