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\).
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\).
- Note that we allow the possibility that \(a_d\equiv0\), so that \(f(x)\) has degree less than \(d\).
- 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\).
- 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\).
- 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.
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.
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\).