Lagrange's theorem (number theory) explained

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

style f \in Z [x] , either:

• every coefficient of is divisible by p, or

p \mid f(x) has at most solutions in,

where is the degree of .

This can be stated with congruence classes as follows: for all polynomials

style f \in ( Z /p Z )[x] with p prime, either:

• every coefficient of is null, or

f(x) =0 has at most solutions in Z /p Z .

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

Proof

Let

style f \in Z [x] be an integer polynomial, and write the polynomial obtained by taking its coefficients . Then, for all integers x,f(x) \equiv 0 \pmod{p} \Longleftrightarrow g(x) \equiv 0 \pmod{p} .

Furthermore, by the basic rules of modular arithmetic,

f(x) \equiv 0 \pmod{p} \Longleftrightarrow f(x \pmod{p}) \equiv 0 \pmod{p} \Longleftrightarrow 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 then f has no roots and the statement is true.

If without roots then the statement is also trivially true.

Otherwise, and f has a root

k\in Z /p 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 style g \in ( Z /p Z )[x] (of degree lower than that of f) and of a constant style r \in Z /p Z (of degree lower than 1) such thatf(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 in number. This proves the result.

References

• Book: LeVeque, William J. . William J. LeVeque

. William J. LeVeque . Topics in Number Theory, Volumes I and II . Dover Publications . New York . 2002 . 1956 . 978-0-486-42539-9 . 1009.11001 . 42 .

• Book: Tattersall, James J. . Elementary Number Theory in Nine Chapters . 2nd . . 2005 . 0-521-85014-2 . 1071.11002 . 198 .