6.1 Lagrange’s Theorem

The arithmetic of ${\mathbb Z}_p$

We saw in Corollary 5.32 that a linear congruence $ax\equiv b\text{ mod }(n)$ has a unique solution $\text{mod }(n)$ if $\gcd(a,n)=1$. Now if $n$ is a prime $p$, then $\gcd(a,n)=\gcd(a,p)$ is either $1$ or $p$. In the former case, we have a unique solution $\text{mod }(p)$, while in the latter case either every $x$ is a solution (when $p\,|\,b$) or no $x$ is a solution (when $p\nmid\;b$).

Looking at this from another point of view, the polynomial $ax-b$ of degree $d=1$ over ${\mathbb Z}_p$ ($a\text{ or }b\not\equiv 0\text{ mod }(p)$), then it has at most one root in ${\mathbb Z}_p$. Now in the Linear Algebra module, we learn that a non-trivial polynomial of degree $d$, with real or complex coefficients, has at most $d$ distinct roots in ${\mathbb R}$ or ${\mathbb C}$. Our first main theorem, due to Lagrange, states that this is also true for the number system ${\mathbb Z}_p$.

Theorem 6.1 (Lagrange’s Theorem)

Let $p$ be prime, and let $f(x)=a_dx^d+\cdots+a_1x+a_0$ be a polynomial with integer coefficients, where $a_i\not\equiv 0\text{ mod }(p)$ for some $i$. Then the congruence $f(x)\equiv 0\text{ mod }(p)$ is satisfied by at most $d$ congruence classes $[x]\in{\mathbb Z}_p$.

1. Note that we allow the possibility that $a_d\equiv0$, so that $f(x)$ has degree less than $d$.
2. Even if $a_d\not\equiv 0$, $f(x)$ may still have fewer than $d$ roots in ${\mathbb Z}_p$. For example, $f(x)=x^2+1$ has only one root in ${\mathbb Z}_2$, namely the class $[1]$, and it has no roots in ${\mathbb Z}_3$.
3. The condition that $a_i\not\equiv 0$ for some $i$ ensures that $f(x)$ yields a non-trivial polynomial when we reduce it $\text{mod }(p)$. If $a_i\equiv 0$ for all $i$ then all $p$ classes $[x]\in{\mathbb Z}_p$ satisfy $f(x)\equiv 0$, so the result will fail if $d<p$.
4. If $p$ is not prime the polynomial may have more than $d$ roots. For example, the polynomial $f(x)=x^2-1$, of degree $d=2$, has four roots in ${\mathbb Z}_8$, namely the classes $[1], [3], [5]$ and $[7]$.

Proof. We use induction on $d$. If $d=0$ then $f(x)=a_0$ with $p$ not dividing $a_0$, so there are no solutions of $f(x)\equiv 0$, as required. For the inductive step, we now assume that $d\geq 1$, and that all polynomials $g(x)=b_{d-1}x^{d-1}+\cdots+b_0$ with some $b_i\not\equiv 0$ have at most $d-1$ roots $[x]\in{\mathbb Z}_p$.

If the congruence $f(x)\equiv 0$ has no solutions, there is nothing left to prove, so suppose that $[a]$ is a solution; thus $f(a)\equiv 0$, so $p$ divides $f(a)$. Now $$f(x)-f(a)=\sum_{i=0}^da_ix^i-\sum_{i=0}^da_ia^i=\sum_{i=0}^da_i(x^i-a^i) =\sum_{i=1}^da_i(x^i-a^i)\,.$$ For each $i=2, \ldots, d$ we can put $$x^i-a^i=(x-a)(x^{i-1}+ax^{i-2}+\cdots+a^{i-2}x+a^{i-1})\,.$$ By taking out the common factor $x-a$ we have $$f(x)-f(a)=(x-a)g(x)$$ for some polynomial $g(x)$ with integer coefficients, of degree at most $d-1$. Now $p$ cannot divide all the coefficients of $g(x)$: if it did, then since it also divides $f(a)$, it would have to divide all the coefficients of $f(x)=f(a)+(x-a)g(x)$, against our assumption. We may therefore apply the induction hypothesis to $g(x)$, so that at most $d-1$ classes $[x]$ satisfy $g(x)\equiv 0$.

We now count classes $[x]$ satisfying $f(x)\equiv 0$: if any class $[x]=[b]$ satisfies $f(b)\equiv 0$, then $p$ divides both $f(a)$ and $f(b)$, so it divides $f(b)-f(a)=(b-a)g(b)$; since $p$ is prime $p$ divides $b-a$ or $g(b)$, so either $[b]=[a]$ or $g(b)\equiv 0$. There are at most $d-1$ classes $[b]$ satisfying $g(b)\equiv 0$, and hence at most $1+(d-1)=d$ satisfying $f(b)\equiv 0$, as required.

Exercise 6.2

Find the roots of the polynomial $f(x)=x^2+1$ in ${\mathbb Z}_p$ for each prime $p\leq 17$. Make a conjecture about how many roots $f(x)$ has in ${\mathbb Z}_p$ for each prime $p$.

We shall revisit this exercise shortly.

Corollary 6.3

Let $f(x)=a_dx^d+\cdots+a_1x+a_0$ be a polynomial with integer coefficients, and let $p$ be prime. If $f(x)$ has more than $d$ roots in ${\mathbb Z}_p$, then each coefficient $a_i\equiv 0\text{ mod }p$.