## Polynomials over The polynomials has four roots in , namely , , , and . In contrast, the following proposition shows that a polynomial of degree over a field, such as , can have at most roots.

Proposition 2.5 (Root Bound)   Let be a nonzero polynomial over a field . Then there are at most elements such that .

Proof. We prove the proposition by induction on . The cases in which are clear. Write . If then     for some polynomial . Next suppose that with . Then , so, since and is a field, we have . By our inductive hypothesis, has at most roots, so there are at most possibilities for . It follows that has at most roots. SAGE Example 2.5   We use SAGE to find the roots of a polynomials over .
sage: R.<x> = PolynomialRing(Integers(13))
sage: f = x^15 + 1
sage: f.roots()
[(12, 1), (10, 1), (4, 1)]
sage: f(12)
0

The output of the roots command above lists each root along with its multiplicity (which is 1 in each case above).

Proposition 2.5   Let be a prime number and let be a divisor of . Then has exactly roots in .

Proof. Let . We have    where and . Theorem 2.1.19 implies that has exactly roots in , since every nonzero element of is a root! By Proposition 2.5.3 has at most roots and has at most roots. Since a root of is a root of either or and has roots, must have exactly roots and must have exactly roots, as claimed. SAGE Example 2.5   We use SAGE to illustrate the proposition.
sage: R.<x> = PolynomialRing(Integers(13))
sage: f = x^6 + 1
sage: f.roots()
[(11, 1), (8, 1), (7, 1), (6, 1), (5, 1), (2, 1)]


We pause to reemphasize that the analogue of Proposition 2.5.5 is false when is replaced by a composite integer , since a root mod of a product of two polynomials need not be a root of either factor. For example, has the four roots , , , and .

William 2007-06-01