In number theory, Lagrange's theorem is a statement named after Joseph-Louis Lagrange about how frequently a polynomial over the integers may evaluate to a multiple of a fixed prime p. More precisely, it states that for all integer polynomials , either: every coefficient of is divisible by p, or has at most solutions in ,
where is the degree of .
This can be stated with congruence classes as follows: for all polynomials with p prime, either: every coefficient of is null, or has at most solutions in .
If p is not prime, then there can potentially be more than solutions. Consider for example p=8 and the polynomial f(x)=x−1, where 1, 3, 5, 7 are all solutions.
Proof
Let be an integer polynomial, and write the polynomial obtained by taking its coefficients . Then, for all integers x,
.
Furthermore, by the basic rules of modular arithmetic,
.
Both versions of the theorem (over and over ) are thus equivalent. We prove the second version by induction on the degree, in the case where the coefficients of f are not all null.
If then has no roots and the statement is true.
If without roots then the statement is also trivially true.
Otherwise, and has a root . The fact that is a field allows to apply the division algorithm to and the polynomial (of degree 1), which yields the existence of a polynomial (of degree lower than that of ) and of a constant (of degree lower than 1) such that
Evaluating at provides .Factor theorem#Proof_3 The other roots of f are then roots of g as well, which by the induction property are at most in number. This proves the result.
Generalization
Let be a polynomial over an integral domain with degree . Then the polynomial equation has at most roots in . Theorem 1.7.
References