Lagrange's theorem (number theory)
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,
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.
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 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, which yields the existence of a polynomial and of a constant such that
Evaluating at provides. 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.