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 is a polynomial with integer coefficients, then either:
where is the degree of. 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 solutions.

A proof of Lagrange's theorem

The two key ideas are the following. Let be the polynomial obtained from by taking the coefficients. Now:
  1. is divisible by if and only if ; and
  2. has no more than roots.
More rigorously, start by noting that if and only if each coefficient of is divisible by. Assume ; its degree is thus well-defined. It is easy to see. To prove, first note that we can compute either directly, i.e. by plugging in and performing arithmetic in, or by reducing. Hence if and only if, i.e. if and only if is divisible by. To prove, note that is a field, which is a standard fact. 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 everything together, the number of incongruent solutions by is the same as the number of roots of, which by is at most, which is at most.