Lagrange's theorem (number theory)

From Wikipedia, the free encyclopedia

This article is about Lagrange's theorem in number theory. See also Lagrange's theorem (group theory).

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 analogous to the fundamental theorem of algebra, which is applied to the roots of complex polynomials.

Lagrange's theorem is named after Joseph Lagrange.