Lagrange's theorem (number theory)

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

In number theory, Lagrange's theorem states that:

If p is a prime number and $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 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.

Without loss of generality 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}$).