Lagrange's theorem (number theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 is a polynomial with integer coefficients, then either:

  • every coefficient of f(x) is divisible by p, or
  • 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[edit]

The two key ideas are the following. Let be the polynomial obtained from by taking the coefficients . Now (i) is divisible by if and only if ; (ii) has no more roots than its degree.

More rigorously, start by noting that if and only if each coefficient of is divisible by . Assume is not 0; its degree is thus well-defined. It's easy to see . To prove (i), first note that we can compute either directly, i.e. by plugging in (the residue class of) and performing arithmetic in , or by reducing . Hence if and only if , i.e. if and only if is divisible by . To prove (ii), note that is a field, which is a standard fact; a quick proof is to note that since is prime, 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 are incongruent if and only if . Putting it all together: the number of incongruent solutions by (i) is the same as the number of roots of , which by (ii) is at most , which is at most .