Lagrange's theorem (number theory)

In number theory, Lagrange's theorem states that:

f(x)

is an integer polynomial over

\mathbb {Z} /p

of degree n and not identically equal to zero (with at least one coefficient not divisible by p), then

f(x)\equiv 0{\pmod {p}}

has at most n solutions in

\mathbb {Z} /p

.

If the modulus is not prime, then it is possible for there to be more than n solutions. The exact number of solutions can be determined by finding the prime factorization of n. We then split the polynomial congruence into several polynomial congruences, one for each distinct prime factor, and find solutions modulo powers of the prime factors. Then, the number of solutions is equal to the product of the number of solutions for each individual congruence.

Lagrange's theorem is named after Joseph-Louis Lagrange.

A proof of Lagrange's theorem

Proceed by induction on n, noting that it is trivially true for n = 0.

Assuming it is true for n = k, consider a non-zero polynomial $f(x)=\sum _{i=0}^{k+1}{a_{i}x^{i}}$ , deg(f) = k + 1, with m roots.

If m = 0 then f has no roots, so in particular it has less than k + 1 roots. If m > 0, so there is an r such that $f(r)=0$ .

So $f(x)=f(x)-f(r)=\sum _{i=0}^{k+1}{a_{i}\left(x^{i}-r^{i}\right)}=(x-r)g(x)$ for some polynomial g with deg(g) = k. Clearly $g(x)$ is not identically zero, so $g(x)$ has at most k roots.

Since $(x-r)$ has precisely one root, $f(x)$ has at most k + 1 roots and the proof is complete.

Extension

The theorem and proof given above generalize to arbitrary fields, having multiplicative inverses for all non-zero elements (for example, $\mathbb {R}$ ).

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.