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 \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_p 0 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 \textstyle g(x) \in (\mathbb{Z}/p)[x] be the polynomial obtained from f(x) by taking the coefficients \mod 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) \mod 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).