Lagrange's theorem (number theory)
From Wikipedia, the free encyclopedia
For Lagrange's other theorems, see 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 , either:
- every coefficient of f is divisible by p, or
has at most deg f solutions in {1, 2, ..., p},
where deg f is the degree of f.
This can be stated with congruence classes as follows: for all polynomials with p prime, either:
- every coefficient of f is null, or
has at most deg f solutions in
.
If p is not prime, then there can potentially be more than deg f(x) solutions. Consider for example p=8 and the polynomial f(x)=x2-1, where 1, 3, 5, 7 are all solutions.