Lagrange's Theorem (Number Theory)

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {\Z_p, +_p, \times_p}$ be the ring of integers modulo $p$ for some prime $p$.

Let $f$ be a polynomial in one variable of degree $n$ over $\Z_p$.

Then $f$ has at most $n$ roots in $\Z_p$.


Proof

Proof by induction on $n$:

Basis for the Induction

When $n = 1$, we have:

$\map f x = a x + b$ for some $a, b \in \Z_p$ and $a \ne 0$

Suppose $x_1, x_2 \in \Z_p$ are two roots of $\map f x$.

Then:

\(\ds a x_1 + b\) \(\equiv\) \(\ds a x_2 + b\) \(\ds \equiv 0\) \(\ds \pmod p\)
\(\ds \leadsto \ \ \) \(\ds a x_1\) \(\equiv\) \(\ds a x_2\) \(\ds \pmod p\)
\(\ds \leadsto \ \ \) \(\ds x_1\) \(\equiv\) \(\ds x_2\) \(\ds \pmod p\) since $a \perp p$

Hence these two roots must be the same, implying that there is at most $1$ root.

This is our basis for the induction.


Induction Hypothesis

This is our induction hypothesis:

A polynomial in one variable of degree $k$ has at most $k$ roots in $\Z_p$.

It is to be demonstrated that:

A polynomial in one variable of degree $k + 1$ has at most $k + 1$ roots in $\Z_p$.


Induction Step

This is our induction step:

Consider $n = k + 1$, and let $f$ be a polynomial in one variable of degree $k + 1$.

If $f$ does not have a root in $\Z_p$, our claim is satisfied.


Otherwise, suppose $f$ does have a root $x_0$.

From Ring of Integers Modulo Prime is Field, $\Z_p$ is a field.

Applying the Polynomial Factor Theorem, since $\map f {x_0} = 0$:

$\map f x = \paren {x - x_0} \map Q x$

where $Q$ is a polynomial of degree $k$.


By Euclid's Lemma for Prime Divisors:

$\map f x = 0 \iff x - x_0 = 0 \text { or } \map Q x = 0$

By the induction hypothesis, $Q$ has at most $k$ roots.

Hence $f$ has at most $k + 1$ roots.


By the Principle of Mathematical Induction, the theorem holds for all $n$.

$\blacksquare$


Examples

Non-Prime Index

This does not hold for composite number $p$.

For $p = 8$, the polynomial $x^2 - 1$ has $4$ roots $\eqclass 1 8, \eqclass 3 8, \eqclass 5 8, \eqclass 7 8$ in $\Z_p$ and $4 > n = 2$.


Source of Name

This entry was named for Joseph Louis Lagrange.