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 satisfiesConsequently, 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 isThus is a quadratic residue for and a quadratic nonresidue for .
Apply Gauss's lemma to the representatives . With , exactlyexceed . 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 defineIf 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 ofabove 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
Articles by others on the same topic
There are currently no matching articles.