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. More precisely, it states that if p is a prime number, [math]\displaystyle{ x \in \mathbb{Z}/p\mathbb{Z} }[/math], and [math]\displaystyle{ \textstyle f(x) \in \mathbb{Z}[x] }[/math] is a polynomial with integer coefficients, then either:

• every coefficient of f(x) is divisible by p, or
• f(x) ≡ 0 (mod p) has at most deg f(x) solutions

where deg f(x) is the degree of f(x). If the modulus is not prime, then it is possible for there to be more than deg f(x) solutions.

Proof

The two key ideas are the following. Let g(x) ∈ (Z/pZ)[x] be the polynomial obtained from f(x) by taking the coefficients mod p. Now:

1. f(k) is divisible by p if and only if g(k) = 0; and
2. g(x) has no more than deg g(x) roots.

More rigorously, start by noting that g(x) = 0 if and only if each coefficient of f(x) is divisible by p. Assume g(x) ≠ 0; its degree is thus well-defined. It is easy to see deg g(x) ≤ deg f(x). To prove (1), first note that we can compute g(k) either directly, i.e. by plugging in (the residue class of) k and performing arithmetic in Z/pZ, or by reducing f(k) mod p. Hence g(k) = 0 if and only if f(k) ≡ 0 (mod p), i.e. if and only if f(k) is divisible by p. To prove (2), note that Z/pZ is a field, which is a standard fact (a quick proof is to note that since p is prime, Z/pZ is a finite integral domain, hence is a field). Another standard fact is that a non-zero polynomial over a field has at most as many roots as its degree; this follows from the division algorithm.

Finally, note that two solutions f(k₁) ≡ f(k₂) ≡ 0 (mod p) are incongruent if and only if [math]\displaystyle{ k_1 \not\equiv k_2 }[/math] (mod p). Putting everything together, the number of incongruent solutions by (1) is the same as the number of roots of g(x), which by (2) is at most deg g(x), which is at most deg f(x).

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. https://archive.org/details/topicsinnumberth0000leve/page/42. 
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (2nd ed.). Cambridge University Press. p. 198. ISBN 0-521-85014-2.