Lagrange's theorem (number theory)

For Lagrange's other theorems, see Lagrange's theorem (disambiguation).

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 $\textstyle f\in \mathbb {Z} [x]$, either:

• every coefficient of f is divisible by p, or
• $p\mid f(x)$ has at most deg f solutions in {1, 2, ..., p},

where deg f is the degree of f.

This can be stated with congruence classes as follows: for all polynomials $\textstyle f\in (\mathbb {Z} /p\mathbb {Z} )[x]$ with p prime, either:

• every coefficient of f is null, or
• $f(x)=0$ has at most deg f solutions in $\mathbb {Z} /p\mathbb {Z}$.

If p is not prime, then there can potentially be more than deg f(x) solutions. Consider for example p=8 and the polynomial f(x)=x²-1, where 1, 3, 5, 7 are all solutions.

Proof

Let $\textstyle f\in \mathbb {Z} [x]$ be an integer polynomial, and write g ∈ (Z/pZ)[x] the polynomial obtained by taking its coefficients mod p. Then, for all integers x,

$f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x)\equiv 0{\pmod {p}}$.

Furthermore, by the basic rules of modular arithmetic,

$f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad f(x{\pmod {p}})\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x{\pmod {p}})\equiv 0{\pmod {p}}$.

Both versions of the theorem (over Z and over Z/pZ) 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 deg f = 0 then f has no roots and the statement is true.

If deg f ≥ 1 without roots then the statement is also trivially true.

Otherwise, deg f ≥ 1 and f has a root $k\in \mathbb {Z} /p\mathbb {Z}$. The fact that Z/pZ is a field allows to apply the division algorithm to f and the polynomial X-k (of degree 1), which yields the existence of a polynomial $\textstyle g\in (\mathbb {Z} /p\mathbb {Z} )[x]$ (of degree lower than that of f) and of a constant $\textstyle r\in \mathbb {Z} /p\mathbb {Z}$ (of degree lower than 1) such that

$f(x)=g(x)(x-k)+r.$

Evaluating at x=k provides r=0. The other roots of f are then roots of g as well, which by the induction property are at most deg g ≤ deg f - 1 in number. This proves the result.

References

• LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. p. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (2nd ed.). Cambridge University Press. p. 198. ISBN 0-521-85014-2. Zbl 1071.11002.