Loading AI tools
From Wikipedia, the free encyclopedia
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 p. More precisely, it states that for all integer polynomials , either:
where deg f is the degree of f.
This can be stated with congruence classes as follows: for all polynomials with p prime, either:
If p is not prime, then there can potentially be more than deg f(x) solutions. Consider for example p=8 and the polynomial f(x)=x2-1, where 1, 3, 5, 7 are all solutions.
Let be an integer polynomial, and write g ∈ (Z/pZ)[x] the polynomial obtained by taking its coefficients mod p. Then, for all integers x,
.
Furthermore, by the basic rules of modular arithmetic,
.
Both versions of the theorem (over Z and over Z/pZ) are thus equivalent. We prove the second version by induction on the degree, in the case where the coefficients of f are not all null.
If deg f = 0 then f has no roots and the statement is true.
If deg f ≥ 1 without roots then the statement is also trivially true.
Otherwise, deg f ≥ 1 and f has a root . The fact that Z/pZ is a field allows to apply the division algorithm to f and the polynomial x-k (of degree 1), which yields the existence of a polynomial (of degree lower than that of f) and of a constant (of degree lower than 1) such that
Evaluating at x=k provides r=0. The other roots of f are then roots of g as well, which by the induction property are at most deg g ≤ deg f - 1 in number. This proves the result.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.