In mathematics, there is more than one Gauss lemma; all are named after Carl Friedrich Gauss.

In the theory of polynomials, the Gauss lemma relates the highest common factor of a product of two polynomials with integer coefficients to the corresponding hcfs of the factors. If we are looking at R = P.Q then any common factor of the coefficients of P will divide all the coefficients of R, by an easy proof. The lemma works the other way round, limiting the common factors for R. It supplies what is needed to conclude that the hcf of the coefficients of R is exactly the product of the hcfs for P and for Q.

A statement that is equivalent: if the hcf for P and for Q is 1, then it is 1 for R, also.

In the case of one variable there is a simple proof of this. Consider a prime number p, and try to show that R mod p (i.e. R with coefficients reduced to the field of residues modulo p) is not 0. In fact the degree of R mod p is the sum of those of P mod p and of Q mod p, which is more than enough, because we are working in a field.

An important consequence is that R can only factorise as a product of polynomials with rational number coefficients, if it already does into integer polynomials. One sees this by checking the powers of a fixed prime p needed to clear denominators; the same argument works as before, and this version can also be called the Gauss lemma. It applies to the rational root theorem.

There is a generalisation to several variables.

The Gauss lemma in number theory is involved in some proofs of quadratic reciprocity.

For any odd prime p let a be an integer that is relatively prime to p.

Consider the integers

and their least positive residues modulo m.

Let n be the number of these residues that are greater than p/2. Then

where (a/p) is the Legendre symbol.

This can, for example, be applied immediately when a = −1, giving

n = ½(p − 1).

From a sophisticated point of view, this is a case of the transfer.