Gauss's Lemma

Let the multiples m, 2m, ..., [(p-1)/2]m of an integer such that pm be taken. If there are an even number r of least positive residues mod p of these numbers >p/2, then m is a quadratic residue of p. If r is odd, m is a quadratic nonresidue. Gauss's lemma can therefore be stated as (m|p)=(-1)^r, where (m|p) is the Legendre symbol. It was proved by Gauss as a step along the way to the quadratic reciprocity theorem (Nagell 1951).

The following result is known as Euclid's lemma, but is incorrectly termed "Gauss's Lemma" by Séroul (2000, p. 10). Euclid's lemma states that for any two integers a and b, suppose d|ab. Then if d is relatively prime to a, then d divides b.

See also

Euclid's Lemma, Legendre Symbol, Quadratic Reciprocity Theorem

Explore with Wolfram|Alpha


Nagell, T. "Gauss's Lemma." §40 in Introduction to Number Theory. New York: Wiley, pp. 139-141, 1951.Séroul, R. "Gauss's Lemma." §2.4.2 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 10-11, 2000.

Cite this as:

Weisstein, Eric W. "Gauss's Lemma." From MathWorld--A Wolfram Web Resource.

Subject classifications