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. 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) \equiv 0 (mod p)$ has at most $deg f (x)$ incongruent solutions

where $deg f (x)$ is the degree of $f (x)$ . 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 $g (x) \in (Z / p)[x]$ be the polynomial obtained from $f (x)$ by taking the coefficients $mod p$ . Now:

$f (k)$ is divisible by $p$ if and only if $g (k) = 0$ ; and
$g (x)$ has no more than $deg g (x)$ roots.

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) \neq 0$ ; its degree is thus well-defined. It is easy to see $deg g (x) \leq deg f (x)$ . To prove (1), 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) \equiv 0 (mod p)$ , i.e. if and only if $f (k)$ is divisible by $p$ . To prove (2), 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) \equiv f (k 2) \equiv 0 (mod p)$ are incongruent if and only if $k_{1}\not \equiv k_{2}$ $(mod p)$ . Putting everything together, the number of incongruent solutions by (1) is the same as the number of roots of $g (x)$ , which by (2) 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.