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. More precisely, it states that if p is a prime number and
f
(
x
)
∈
Z
[
x
]
is a polynomial with integer coefficients, then either:
every coefficient of f(x) is divisible by p, or
f
(
x
)
≡
p
0
has at most deg f(x) incongruent solutions.
Solutions are "incongruent" if they do not differ by a multiple of p. If the modulus is not prime, then it is possible for there to be more than deg f(x) solutions.
The two key ideas are the following. Let
g
(
x
)
∈
(
Z
/
p
)
[
x
]
be the polynomial obtained from
f
(
x
)
by taking the coefficients
mod
p
. Now (i)
f
(
k
)
is divisible by
p
if and only if
g
(
k
)
=
0
; (ii)
g
(
k
)
has no more roots than its degree.
More rigorously, start by noting that
g
(
x
)
=
0
if and only if each coefficient of
f
(
x
)
is divisible by
p
. Assume
g
(
x
)
is not 0; its degree is thus well-defined. It's easy to see
deg
g
(
x
)
≤
deg
f
(
x
)
. To prove (i), first note that we can compute
g
(
k
)
either directly, i.e. by plugging in (the residue class of)
k
and performing arithmetic in
Z
/
p
, or by reducing
f
(
k
)
mod
p
. Hence
g
(
k
)
=
0
if and only if
f
(
k
)
≡
p
0
, i.e. if and only if
f
(
k
)
is divisible by
p
. To prove (ii), note that
Z
/
p
is a field, which is a standard fact; a quick proof is to note that since
p
is prime,
Z
/
p
is a finite integral domain, hence is a field. Another standard fact is that a non-zero polynomial over a field has at most as many roots as its degree; this follows from the division algorithm.
Finally, note that two solutions
f
(
k
1
)
,
f
(
k
2
)
≡
p
0
are incongruent if and only if
k
1
≢
p
k
2
. Putting it all together: the number of incongruent solutions by (i) is the same as the number of roots of
g
(
x
)
, which by (ii) is at most
deg
g
(
x
)
, which is at most
deg
f
(
x
)
.
