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

Ancestors (6)

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

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.