# Lagrange's theorem (number theory)

{{#invoke:Hatnote|hatnote}} 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 ${\displaystyle \textstyle f(x)\in \mathbb {Z} [x]}$ is a polynomial with integer coefficients, then either:

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 ${\displaystyle \textstyle g(x)\in (\mathbb {Z} /p)[x]}$ be the polynomial obtained from ${\displaystyle f(x)}$ by taking the coefficients ${\displaystyle \mod p}$. Now (i) ${\displaystyle f(k)}$ is divisible by ${\displaystyle p}$ if and only if ${\displaystyle g(k)=0}$; (ii) ${\displaystyle g(k)}$ has no more roots than its degree.

More rigorously, start by noting that ${\displaystyle g(x)=0}$ if and only if each coefficient of ${\displaystyle f(x)}$ is divisible by ${\displaystyle p}$. Assume ${\displaystyle g(x)}$ is not 0; its degree is thus well-defined. It's easy to see ${\displaystyle \textstyle \deg g(x)\leq \deg f(x)}$. To prove (i), first note that we can compute ${\displaystyle g(k)}$ either directly, i.e. by plugging in (the residue class of) ${\displaystyle k}$ and performing arithmetic in ${\displaystyle \textstyle \mathbb {Z} /p}$, or by reducing ${\displaystyle f(k)\mod p}$. Hence ${\displaystyle g(k)=0}$ if and only if ${\displaystyle f(k)\equiv _{p}0}$, i.e. if and only if ${\displaystyle f(k)}$ is divisible by ${\displaystyle p}$. To prove (ii), note that ${\displaystyle \textstyle \mathbb {Z} /p}$ is a field, which is a standard fact; a quick proof is to note that since ${\displaystyle p}$ is prime, ${\displaystyle \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 ${\displaystyle \textstyle f(k_{1}),f(k_{2})\equiv _{p}0}$ are incongruent if and only if ${\displaystyle \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 ${\displaystyle g(x)}$, which by (ii) is at most ${\displaystyle \deg g(x)}$, which is at most ${\displaystyle \deg f(x)}$.

## References

• {{#invoke:citation/CS1|citation

|CitationClass=book }}

• {{#invoke:citation/CS1|citation

|CitationClass=book }}