## 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