Lagrange's theorem (number theory)

From Wikipedia, the free encyclopedia

Lagrange's theorem, in the mathematics of number theory, states that:

If p is a prime number and f(x) is a polynomial of degree n, then f(x) = 0 (mod p) has at most n integral solutions for 0 < x < p .

If the modulus is not prime, then it is possible for there to be more than n solutions. The exact number of solutions can be determined by finding the prime factorization of n. We then split the polynomial congruence into several polynomial congruences, one for each distinct prime factor, and find solutions mod powers of the prime factors. Then, the number of solutions is equal to the product of the number of solutions for each individual congruence.

Lagrange's theorem is named after Joseph Lagrange.