Lagrange's theorem (number theory)

For Lagrange's theorem, 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. More precisely, it states that if p is a prime number and $\textstyle f(x)\in \mathbb {Z} [x]$ is a polynomial with integer coefficients, then either:

• every coefficient of f(x) is divisible by p, or
• f(x) ≡ 0 (mod p) 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.

A proof of Lagrange's theorem

The two key ideas are the following. Let $\textstyle g(x)\in (\mathbb {Z} /p)[x]$ be the polynomial obtained from $f(x)$ by taking the coefficients ${\bmod {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 $\textstyle \deg g(x)\leq \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 $\textstyle \mathbb {Z} /p$, or by reducing $f(k){\bmod {p}}$. Hence $g(k)=0$ if and only if $f(k)\equiv _{p}0$, i.e. if and only if $f(k)$ is divisible by $p$. To prove (ii), note that $\textstyle \mathbb {Z} /p$ is a field, which is a standard fact; a quick proof is to note that since $p$ is prime, $\textstyle \mathbb {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 $\textstyle f(k_{1}),f(k_{2})\equiv _{p}0$ are incongruent if and only if $\textstyle k_{1}\not \equiv _{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)$.

References

• LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. p. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (2nd ed.). Cambridge University Press. p. 198. ISBN 0-521-85014-2. Zbl 1071.11002.