Misplaced Pages

Lagrange's theorem (number theory)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
For Lagrange's other theorems, 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 p. More precisely, it states that for all integer polynomials f ∈ Z [ x ] {\displaystyle \textstyle f\in \mathbb {Z} } , either:

  • every coefficient of f is divisible by p, or
  • p ∣ f ( x ) {\displaystyle p\mid f(x)} has at most deg f solutions in {1, 2, ..., p},

where deg f is the degree of f.

This can be stated with congruence classes as follows: for all polynomials f ∈ ( Z / p Z ) [ x ] {\displaystyle \textstyle f\in (\mathbb {Z} /p\mathbb {Z} )} with p prime, either:

  • every coefficient of f is null, or
  • f ( x ) = 0 {\displaystyle f(x)=0} has at most deg f solutions in Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } .

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)=x-1, where 1, 3, 5, 7 are all solutions.

Proof

Let f ∈ Z [ x ] {\displaystyle \textstyle f\in \mathbb {Z} } be an integer polynomial, and write g ∈ (Z/pZ) the polynomial obtained by taking its coefficients mod p. Then, for all integers x,

f ( x ) ≡ 0 ( mod p ) ⟺ g ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x)\equiv 0{\pmod {p}}} .

Furthermore, by the basic rules of modular arithmetic,

f ( x ) ≡ 0 ( mod p ) ⟺ f ( x mod p ) ≡ 0 ( mod p ) ⟺ g ( x mod p ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad f(x{\bmod {p}})\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x{\bmod {p}})\equiv 0{\pmod {p}}} .

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 k ∈ Z / p Z {\displaystyle k\in \mathbb {Z} /p\mathbb {Z} } . 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 g ∈ ( Z / p Z ) [ x ] {\displaystyle \textstyle g\in (\mathbb {Z} /p\mathbb {Z} )} (of degree lower than that of f) and of a constant r ∈ Z / p Z {\displaystyle \textstyle r\in \mathbb {Z} /p\mathbb {Z} } (of degree lower than 1) such that

f ( x ) = g ( x ) ( x − k ) + r . {\displaystyle f(x)=g(x)(x-k)+r.}

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.

Generalization

Let p(X) be a polynomial over an integral domain R with degree n > 0. Then the polynomial equation p(x) = 0 has at most n = deg(p(X)) roots in R.

References

  1. Factor theorem#Proof_3
  2. "Polynomials and rings Chapter 3: Integral domains and fields" (PDF). Theorem 1.7.
Categories: