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 (5)

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

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

The Legendre symbol is a mathematical notation that provides a way to determine if a given integer is a quadratic residue modulo a prime number. Specifically, for an integer \( a \) and a prime \( p \), the Legendre symbol is denoted as: \[ \left( \frac{a}{p} \right) \] It is defined as follows: 1. If \( a \) is congruent to 0 modulo \( p \) (i.e.