Lagrange's theorem (number theory)

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

• every coefficient of f is divisible by p, or
• ${\displaystyle p\mid f(x)}$ 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 ${\displaystyle \textstyle f\in (\mathbb {Z} /p\mathbb {Z} )[x]}$ with p prime, either:

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

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)=x²-1, where 1, 3, 5, 7 are all solutions.