Lagrange's theorem (number theory)

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

• every coefficient of Template:Math is divisible by p, or
• $p\mid f(x)$ has at most Template:Math solutions in Template:Math,

where Template:Math is the degree of Template:Math.

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

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

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

Proof

Let $f\in \mathbb{Z}[x]$ be an integer polynomial, and write Template:Math the polynomial obtained by taking its coefficients Template:Math. Then, for all integers x,

$f(x)\equiv 0(\mathrm{mod}p)⟺g(x)\equiv 0(\mathrm{mod}p)$.

Furthermore, by the basic rules of modular arithmetic,

$f(x)\equiv 0(\mathrm{mod}p)⟺f(xmodp)\equiv 0(\mathrm{mod}p)⟺g(xmodp)\equiv 0(\mathrm{mod}p)$.

Both versions of the theorem (over Template:Math and over Template:Math) 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 Template:Math then Template:Mvar has no roots and the statement is true.

If Template:Math without roots then the statement is also trivially true.

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

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

Evaluating at Template:Math provides Template:Math. The other roots of f are then roots of g as well, which by the induction property are at most Template:Math in number. This proves the result.

Generalization

Let Template:Math be a polynomial over an integral domain Template:Mvar with degree Template:Math. Then the polynomial equation Template:Math has at most Template:Math roots in Template:Mvar.

References

• Template:Cite book
• Template:Cite book