Lagrange's Theorem (number Theory)

In number theory, Lagrange's theorem is a statement named after Joseph-Louis Lagrange over the integers may evaluate to a multiple of a fixed prime ''p''. More precisely, it states that for all integer polynomials \textstyle f \in \mathbb /math>, 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 \textstyle f \in (\mathbb/p\mathbb) /math> with ''p'' prime, either:
* every coefficient of is null, or
* $f(x)=0$ has at most solutions in $\mathbb/p\mathbb$.

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 \textstyle f \in \mathbb /math> be an integer polynomial, and write the polynomial obtained by taking its coefficients . Then, for all integers ''x'',

$f(x) \equiv 0 \pmod \quad\Longleftrightarrow\quad g(x) \equiv 0 \pmod$.

Furthermore, by the basic rules of modular arithmetic,

$f(x) \equiv 0 \pmod \quad\Longleftrightarrow\quad f(x \bmod) \equiv 0 \pmod \quad\Longleftrightarrow\quad g(x \bmod) \equiv 0 \pmod$.

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

If without roots then the statement is also trivially true.

Otherwise, and has a root $k\in\mathbb/p\mathbb$.
The fact that is a field allows to apply the division algorithm to and the polynomial (of degree ''1''), which yields the existence of a polynomial \textstyle g \in (\mathbb/p\mathbb) /math> (of degree lower than that of ) and of a constant $\textstyle r \in \mathbb/p\mathbb$ (of degree lower than ''1'') such that

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

Evaluating at provides . 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.

Generalization

Let be a polynomial over an integral domain with degree .
Then the polynomial equation has at most roots in . Theorem 1.7.

References

*
*

{{DEFAULTSORT:Lagrange's Theorem (Number Theory)
Theorems about prime numbers
Theorems about polynomials