Lagrange's theorem (number theory)

{{for|Lagrange's other theorems|Lagrange's theorem (disambiguation)}}

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

every coefficient of {{math|f}} is divisible by p, or
$p \mid f(x)$ has at most {{math|deg f}} solutions in {{math|{{mset|1, 2, ..., p}}}},

where {{math|deg f}} is the degree of {{math|f}}.

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

every coefficient of {{math|f}} is null, or
$f(x)=0$ has at most {{math|deg f}} solutions in $\mathbb{Z}/p\mathbb{Z}$ .

If p is not prime, then there can potentially be more than {{math|deg f(x)}} solutions. Consider for example p=8 and the polynomial f(x)=x{{i sup|2}}−1, where 1, 3, 5, 7 are all solutions.

Proof

Let $\textstyle f \in \mathbb{Z}[x]$ be an integer polynomial, and write {{math|g ∈ (Z/pZ)[x]}} the polynomial obtained by taking its coefficients {{math|mod p}}. Then, for all integers x,

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

Furthermore, by the basic rules of modular arithmetic,

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

Both versions of the theorem (over {{math|Z}} and over {{math|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 {{math|deg f {{=}} 0}} then {{mvar|f}} has no roots and the statement is true.

If {{math|deg f ≥ 1}} without roots then the statement is also trivially true.

Otherwise, {{math|deg f ≥ 1}} and {{mvar|f}} has a root $k\in\mathbb{Z}/p\mathbb{Z}$ .

The fact that {{math|Z/pZ}} is a field allows to apply the division algorithm to {{mvar|f}} and the polynomial {{math|x − k}} (of degree 1), which yields the existence of a polynomial $\textstyle g \in (\mathbb{Z}/p\mathbb{Z})[x]$ (of degree lower than that of {{mvar|f}}) and of a constant $\textstyle r \in \mathbb{Z}/p\mathbb{Z}$ (of degree lower than 1) such that

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

Evaluating at {{math|x {{=}} k}} provides {{math|r {{=}} 0}}.Factor theorem#Proof_3 The other roots of f are then roots of g as well, which by the induction property are at most {{math|deg g ≤ deg f − 1}} in number. This proves the result.

Generalization

Let {{math|p(X)}} be a polynomial over an integral domain {{mvar|R}} with degree {{math|n > 0}}.

Then the polynomial equation {{math|1=p(x) = 0}} has at most {{math|1=n = deg(p(X))}} roots in {{mvar|R}}.{{cite web|url=https://web.mat.bham.ac.uk/R.W.Kaye/teaching/modules/msm203a/chapter3.pdf#page=2|title=Polynomials and rings Chapter 3: Integral domains and fields}} Theorem 1.7.

References

{{cite book | last = LeVeque | first = William J. | title = Topics in Number Theory, Volumes I and II | publisher = Dover Publications | location = New York | year = 2002 | origyear = 1956 | isbn = 978-0-486-42539-9 | zbl = 1009.11001 | page = [https://archive.org/details/topicsinnumberth0000leve/page/42 42] | url = https://archive.org/details/topicsinnumberth0000leve/page/42 }}
{{cite book | title=Elementary Number Theory in Nine Chapters | first=James J. | last=Tattersall | edition=2nd | publisher=Cambridge University Press | year=2005 | isbn=0-521-85014-2 | zbl=1071.11002 | page=198 }}

Category:Theorems about prime numbers

Category:Theorems about polynomials