Skip to main content

Abstract algebra A Kursobjekt for Math 331

Aaron Greicius

Section 2.8 Case study: polynomial rings

The integers furnish us with a nice example where we can completely analyze a rings ideal structure, including its prime and maximal ideals, as well as its quotients. In this section we will look at another case study: polynomial rings \(F[x]\text{,}\) where \(F\) is a field. As you will see, the ideal structure of \(F[x]\) has many similarities with that of the integers. We will see later that these similarities are the result of a deeper similarity between the two rings: namely, that both are examples of Euclidean domains. Our discussion will also include concrete descriptions of the quotients of polynomial rings \(F[x]\text{,}\) which in turn provide us with many new examples of rings to work. In particular, the construction of fields as quotients \(F[x]/M\) where \(M\) is a maximal ideal will play an important role in our development of field theory in Math 331-3.
🔗

Subsection 2.8.1 Division algorithm for polynomials

Although we will mainly be interested in polynomial rings over fields, we begin with a useful result that applies to general polynomial rings.
🔗

Proof.

We need to prove two things: that given any \(g\) there are polynomials \(q,r\) satisfying properties (i) and (ii), and furthermore that the pair \((q,r)\) is unique.
🔗
We begin with existence. Let \(X\) be the set of all pairs of polynomials \((q',r')\) satisfying condition (i) (but not necessarily (ii)). We will show that there is a pair \((q,r)\in X\) that also satisfies (ii). Observe that \(X\) is nonempty, since in particular it contains the pair \((0,g)\text{.}\) If \((q,0)\in X\text{,}\) then this pair satisfies (ii) since \(\deg 0=-\infty< \deg f\) (\(f\) being a nonzero polynomial). Otherwise, let \((q,r)\) be an element of \(X\) for which \(r\) has minimal finite degree. (Such a pair exists since the set \(\{\deg r'\mid (q',r')\in X\}\) is a nonempty subset of \(\Z_{\geq 0}\text{,}\) and hence has a minimal element.) We claim that \(\deg r< \deg f\text{,}\) and hence that \((q,r)\) satisfies (ii). Suppose, by contradiction, that \(r(x)=\bmpoly\) with \(\deg r=m\geq \deg f=n\text{.}\) Since the leading term \(a_n\) of \(f\) is a unit, we can write
\begin{align*} r(x) \amp b_ma_n^{-1}x^{m-n}f(x)+r(x)-b_ma_n^{-1}x^{m-n}f(x)\\ \amp =h(x)f(x)+s(x)\text{,} \end{align*}
where \(h(x)=b_ma_n^{-1}x^{m-n}\text{,}\) and where
\begin{align*} s(x) \amp =r(x)-b_ma_n^{-1}x^{m-n}f(x)\\ \amp = r(x)-b_ma_n^{-1}x^{m-n}(\anpoly)\\ \amp =(b_m-b_m)x^{m}+(b_{m-1}-b_ma_n^{-1}a_{n-1})x^{m-1}+\cdots\\ \amp =(b_{m-1}-b_ma_{n}^{-1}a_{n-1})x^{n-1}+\cdots \end{align*}
has degree at most \(m-1\text{.}\) But then we have
\begin{align*} g\amp =qf+r \\ \amp = qf+hf+s\\ \amp = (q+h)f+s\text{,} \end{align*}
showing that \((q+h,s)\in X\) and \(\deg s< \deg r\text{.}\) This contradicts the minimality of \(\deg r\text{.}\) Thus \(\deg r< \deg f\text{,}\) and we are done.
🔗
We now prove that there is exactly one pair \((q,r)\) satisfying (i) and (ii). Indeed, suppose \((q,r)\) and \((q',r')\) both satisfy these properties. From \(g=qf+r=q'f+r'\text{,}\) it follows that
\begin{align*} (q-q')f \amp =(r'-r)\text{.} \end{align*}
If \(q-q'\ne 0\text{,}\) then since the leading coefficient of \(f\) is a unit, it is easy to see that \(\deg (q-q')f\geq \deg f\text{.}\) But then we would have
\begin{align*} \deg r'-r \amp =\deg (q-q')f \geq \deg f\text{,} \end{align*}
a contradiction since \(\deg (r-r')\leq \max\{\deg r,\deg r'\}< \deg f\text{.}\) Thus \(q-q'=0\text{,}\) from which it follows that \(r'-r=0\text{.}\) We conclude that \(q=q'\) and \(r=r'\text{,}\) and thus that \((q,r)=(q',r')\text{,}\) as desired.
🔗
🔗

Definition 2.8.2. Polynomial division with remainder.

Let \(R\) be a nontrivial commutative ring, and let \(f\in R[x]\) be a nonzero polynomial whose leading coefficient is a unit. Given a polynomial \(g\in R[x]\) we call the unique polynomials \(q\) and \(r\) satisfying the two conditions of Theorem 2.8.1 the quotient and remainder upon division of \(g\) by \(f\text{.}\)
🔗
🔗
The following result is a corollary of the division algorithm theorem, but is important enough to be deemed a theorem.
🔗

Proof.

For (1) it suffices to show that \(\ker\pi \cap R=\{0\}\text{.}\) Since \(\ker \pi=(f)\text{,}\) and since \(\deg gf=\deg g+\deg f\) for any \(g\in R[x]\) (Proposition 2.3.8), it is easy to see that \(gf\in R\) if and only if if \(g=0\) and thus \(gf=0\text{.}\)
🔗
Next, given \(g\in R[x]\) and writing \(g=qf+r\) as in the division algorithm, we see that
\begin{align*} \pi(g) \amp = \pi(qf+r)\\ \amp = \pi(q)\pi(f)+\pi(r)\\ \amp =\pi(r) \amp (\pi(f)=0)\text{.} \end{align*}
This proves (2).
🔗
Lastly, given any \(g\in R[x]\text{,}\) let \(r\) be its remainder upon division by \(f\text{.}\) Since \(\deg r< \deg f=n\text{,}\) we may write
\begin{align*} r(x) \amp =a_0+a_1x+\cdots +a_{n-1}x^{n-1} \end{align*}
for elements \(a_k\in R\text{.}\) From (2) we have
\begin{align*} \overline{g} \amp =\overline{r} \\ \amp = a_0+a_1\overline{x}+\cdots +a_{n-1}\overline{x}^{n-1}\text{.} \end{align*}
Thus every element of the quotient can be expressed in the desired form. Lastly, to see that this expression is unique, if we have
\begin{align*} \overline{g} \amp = \sum_{k=0}^na_k\overline{x}^k=\sum_{k=0}^nb_k\overline{x}^k\text{,} \end{align*}
then we have \(\pi(r)=\pi(s)\text{,}\) where
\begin{align*} r(x) \amp =\sum_{k=0}^na_kx^k\\ s(x) \amp =\sum_{k=0}^nb_kx^k \end{align*}
and thus \(r(x)-s(x)\in \ker\pi=(f)\text{.}\) But any nonzero element of \((f)\) must have degree at least \(n\text{,}\) since \(\deg qf=\deg q+\deg f\geq n\) for any nonzero polynomial \(q\text{.}\) It follows that \(r(x)-s(x)=0\) and thus that \(a_k=b_k\) for all \(k\text{.}\)
🔗
🔗

Remark 2.8.4. Quotients of polynomial rings.

Note that \(R[x]/(f)\) is an \(R\)-algebra, with structural ring homomorphism given by the composition
\begin{align*} R \amp \rightarrow R[x] \rightarrow R[x]/(f)\text{.} \end{align*}
Once we have the language of modules at our disposal, we will be able to summarize (2) of Theorem 2.8.3 by saying that \(R[x]/(f)\) is an \(R\)-algebra that is free of rank \(\deg f\) as an \(R\)-module.
🔗
For now we content ourselves with a special case of this observation. Namely, when \(F\) is a field, then \(F[x]/(f)\) is an \(F\)-algebra and hence an \(F\)-vector space. In this context, (2) of Theorem 2.8.3 tells us that
\begin{align*} B \amp =(1, \overline{x}, \overline{x}^2, \ldots, \overline{x}^{n-1}) \end{align*}
is a basis of \(F[x]/(f)\) as an \(F\)-vector space, and hence that \(\dim F[x]/(f)=n\) as an \(F\)-vector space.
🔗
🔗
🔗

Subsection 2.8.2 Polynomial rings over fields

Definition 2.8.5. Principal ideal domain.

A principal ideal domain (PID) is an integral domain \(R\) in which every ideal is principal.
🔗
🔗
The integers \(\Z\) are the quintessential example of a PID that is not a field. As we now show with the help of the Theorem 2.8.1, polynomial rings over fields furnish us with another interesting example. The proof is very similar to the one we gave for Theorem 1.9.6.
🔗

Proof.

First note that \(F[x]\) is an integral domain since \(F\) is an integral domain, as we have seen previously.
🔗
As always we have \(\{0\}=(0)\) and \(F[x]=(1)\text{.}\) Let \(I\) be a proper nonzero ideal. Since \(I\ne F[x]\text{,}\) it contains no elements of \((F[x])^*=F^*\text{.}\) It follows that the set
\begin{align*} \deg(I-\{0\}) \amp =\{\deg f\mid f\in I\} \end{align*}
is a nonzero subset of \(\Z_{\geq 1}\text{,}\) and thus has a minimal element \(n\geq 1\text{.}\) Let \(f\) be an element of \(I\) with \(\deg f=n\text{.}\) Since \(cf\in I\) for all \(c\in F\text{,}\) we may assume without loss of generality that \(f\) is monic. We will show that \((f)=I\text{.}\) It is clear that \((f)\subseteq I\text{.}\) For the other direction, given any \(g\in I\text{,}\) we may write
\begin{align*} g \amp =qf+r\text{,} \end{align*}
where \(\deg r< \deg f\text{.}\) Since \(r=g-qf\in I\text{,}\) and since \(f\) has minimal degree among elements of \(I-\{0\}\text{,}\) we see that \(r=0\text{,}\) and \(g=qf\in (f)\text{.}\) This proves that \(I\subseteq (f)\) and hence that \(I=(f)\text{.}\)
🔗
We now show that the monic polynomial \(f\) with \(I=(f)\) is unique. Suppose we have \((f)=(g)\) where \(f\) and \(g\) are monic. It follows that \(f\mid g\) and \(g\mid f\text{,}\) or equivalently \(g=pf\) and \(f=qg\) for polynomials \(p,q\in F[x]\text{.}\) From Proposition 2.3.8, we conclude that
\begin{align} \deg g \amp =\deg p+\deg f\leq \deg f\tag{2.8.1}\\ \deg f \amp =\deg q+\deg g\leq \deg g\text{.}\tag{2.8.2} \end{align}
It follows that \(\deg f=\deg g\text{,}\) and hence that \(g=c f\) for some constant \(c\in F^*\text{.}\) Since \(f\) and \(g\) are both monic, we conclude that \(c=1\) and \(f=g\text{.}\)
🔗
🔗

Definition 2.8.7. Divisibility.

Let \(R\) be a ring. Given elements \(a,b\in R\text{,}\) we say that \(a\) divides \(b\) in \(R\) (or \(b\) is a multiple of \(a\) in \(R\)), written \(a\mid b\text{,}\) if there is an element \(r\in R\) satisfying \(b=ra\text{.}\)
🔗
🔗

Definition 2.8.8. Prime and irreducible elements.

Let \(R\) be an integral domain.
🔗
A nonzero element \(p\in R-\{0\}\) is prime if \(p\mid ab\) implies \(p\mid a\) or \(p\mid b\) for all \(a,b\in R\text{.}\) Equivalently, \(p\) is prime if the ideal \((p)\) is a nonzero prime ideal.
🔗
A nonzero, non-unit element \(r\in R-R^*-\{0\}\) is irreducible if \(r=ab\) implies \(a\in R^*\) or \(b\in R^*\text{.}\)
🔗
Elements \(a,b\in R\) are associates if \(a=ub\) for some unit \(u\in R^*\text{.}\)
🔗
🔗

Remark 2.8.9. Prime elements and prime ideals.

Let \(R\) be a commutative ring. It is easy to see that an element \(r\in R\) is prime (as in Definition 2.8.8) if and only if its principal ideal \((r)\) is prime (as in Definition 2.7.5).
🔗
🔗

Proof.

Implication: (1)\(\implies\)(2). Assume \(f\) is irreducible and let \(I\) be an ideal of \(F[x]\) satisfying \((f)\subseteq I\text{.}\) Since \(F[x]\) is a PID, we have \(I=(g)\text{,}\) in which case \((f)\subseteq (g)\) is equivalent to \(g\mid f\text{.}\) Since \(f\) is irreducible, this implies \(g\) is a unit, or \(g=cf\text{,}\) where \(c\) is a unit. But then, either \((g)=F[x]\text{,}\) or \((g)=(f)\text{.}\) This proves \((f)\) is maximal.
🔗
Implication: (2)\(\implies\)(3). This implication is just a special instance of the more general fact that in a commutative ring all maximal ideals are prime ideals.
🔗
Implication: (3)\(\implies\)(1). Assume \((f)\) is prime. As observed in Remark 2.8.9, it follows that \(f\) is a prime element of \(F[x]\text{.}\) Assume \(f=gh\) for some polynomials \(g,h\in F[x]\text{.}\) Since \(f\) is prime, we have \(f\mid g\) or \(f\mid h\text{.}\) In the first case, we have \(g=qf\) and hence \(f=fqh\text{.}\) Since \(F[x]\) is integral and \(f\ne 0\text{,}\) it follows that \(qh=1\) and thus \(h\) is a unit. Similarly, if \(f\mid h\text{,}\) then \(g\) is a unit. Thus \(f=gh\) implies \(g\) is a unit or \(h\) is a unit, and we conclude that \(f\) is irreducible.
🔗
🔗

Remark 2.8.11. Comparing \(\Z\) and \(F[x]\).

Let \(F\) be a field. As should be clear by now there are a number of structural similarities between the rings \(\Z\) and \(F[x]\text{:}\)
  • Both rings are PIDs.
    🔗
    🔗
  • In both rings, a ring element is prime if and only if it is irreducible.
    🔗
    🔗
  • In both rings the prime ideals consist of the zero ideal and ideals of the form \((r)\text{,}\) where \(r\) is irreducible in the ring.
    🔗
    🔗
  • In both rings all nonzero prime ideals are maximal, generated by irreducible (equivalently, prime) elements.
    🔗
    🔗
🔗
🔗
Theorem 2.8.10 allows us to easily produce maximal ideals of a polynomial ring \(F[x]\) (\(F\) a field). This in turn allows us to easily construct new fields as quotients of \(F[x]\) by these maximal ideals. Furthermore, Theorem 2.8.3 gives us a concrete description of these quotients, allowing us to explore the arithmetic of these fields in a hands-on manner.
🔗

Remark 2.8.13. Irreducible polynomials.

Let \(F\) be a field. It is easy to see that a polynomial \(f\in F[x]\) is irreducible if and only if it has no factor \(g\) of positive degree. Although in general it can be quite tricky to determine whether a polynomial is irreducible, for polynomials of degree at most 3, the situation is simpler, as we now summarize.
  • Degree 1.
    Every degree-1 polynomial \(f=ax+b\) is irreducible. Indeed, if \(f=gh\text{,}\) then since
    \begin{align*} 1 \amp =\deg f=\deg g+\deg h\text{,} \end{align*}
    we must have \(\deg g=0\) or \(\deg h=0\text{.}\) But then either \(g\) is a unit or \(h\) is a unit.
    🔗
    🔗
  • Degree 2.
    Let \(f\in F[x]\) be a polynomial of degree 2. To have a nontrivial factorization \(f=gh\text{,}\) the same degree argument above implies that both \(g\) and \(h\) must be linear. Note that any linear polynomial \(g(x)=ax+b\) has a root in \(F\) (namely \(-b/a\)). As a result, it follows that a polynomial \(f\) has a linear factor if and only if we have \(f(c)=0\) for some \(c\in F\text{:}\) i.e., if and only if \(f\) has a root in \(F\text{.}\) We conclude that a degree-2 polynomial is irreducible if and only if it has no roots in \(F\text{.}\)
    🔗
    🔗
  • Degree 3.
    Again, looking at degrees, we see that if \(f\in F[x]\) is a degree-3 polynomial, then \(f\) has a nontrivial factorization \(f=gh\) if and only if one of the factors is linear. Thus, just as in the degree-2 case, we conclude that a degree-3 polynomial \(f\) is irreducible if and only if it has no roots in \(F\text{.}\)
    🔗
    🔗
Things become more complicated once our polynomials have degree 4 or higher: in particular, being irreducible is no longer equivalent to having no roots. For example, the polynomial \(f(x)=(x^2+1)(x^2+2)\in \R[x]\) is easily seen to have no roots in \(\R\text{,}\) and yet is manifestly reducible.
🔗
🔗

Example 2.8.14. Quotients by linear polynomials.

Let \(F\) be a field, and let \(f(x)=ax+b\) be a linear (i.e., degree-1) polynomial in \(F[x]\text{.}\) Prove: \(F[x]/(f)\cong F\text{.}\)
🔗
Solution.
Let \(\phi\colon F[x]\rightarrow F\) be the surjective ring homomorphism defined as \(\phi(g)=g(-b/a)\text{.}\) Clearly, \(\phi(f)=0\text{,}\) and thus \((f)\subseteq \ker\phi\text{.}\) Since \((f)\) is maximal (\(f\) is irreducible), and \(\ker\phi\ne F[x]\text{,}\) we have \((f)=\ker\phi\text{.}\) By the first isomorphism theorem, we conclude that \(F[x]/(f)\cong F\text{.}\)
🔗
🔗
🔗

Example 2.8.15. Quotients of \(\R[x]\).

Show that \(\R[x]/(x^2+1)\) and \(\R[x]/(x^2+x+1)\) are both fields, and are isomorphic to one another.
🔗
Solution.
From the quadratic formula theorem, we see easily that the polynomials \(x^2+1\) and \(x^2+x+1\) have no roots in \(\R\text{.}\) It follows from Remark 2.8.13 that both polynomials are irreducible in \(\R[x]\text{,}\) and hence that the corresponding quotients are fields. We prove that both are isomorphic to \(\C\text{.}\)
🔗
For \(\R[x]/(x^2+1)\text{,}\) consider the ring homomorphism \(\phi\colon \R[x]\rightarrow \C\) defined as \(\phi(g)=g(i)\text{.}\) The map is clearly surjective, since \(\phi(a+bx)=a+bi\) for all \(a,b\in \R\text{.}\) Furthermore, clearly, \((x^2+1)\subseteq \ker \phi\text{,}\) since \((i)^2+1=-1+1=0\text{;}\) and since \((x^2+1)\) is maximal (\(x^2+1\) is irreducible), it follows that \((x^2+1)=\ker\phi\text{.}\) The claim follows from the first isomorphism theorem.
🔗
Now consider \(\R[x]/(x^2+x+1)\text{,}\) and let
\begin{align*} \omega \amp =e^{2\pi i/3}\\ \amp = \cos(2\pi/3)+i\sin(2\pi /3)\\ \amp = -\frac{1}{2}+\frac{\sqrt{3}}{2}\, i\text{.} \end{align*}
Verify for yourself that \(\omega\) is one of the two complex roots of \(x^2+x+1\text{;}\) \(\overline{\omega}\) is the other. Define \(\phi\colon \R[x]\rightarrow \C\) as \(\phi(g)=g(\omega)\text{.}\) Again, clearly \((x^2+x+1)\subseteq \ker\phi\text{,}\) and since \((x^2+x+1)\) is maximal, we conclude that \(\ker\phi=(x^2+x+1)\) and \(\R[x]/(x^2+x+1)\cong \im \phi\text{.}\) We claim that \(\im\phi=\C\text{.}\) This is not as obvious as in the previous case. However, from Theorem 2.8.3, we know that \(\im \phi\) is a \(2\)-dimensional \(\R\)-subspace of \(\C\text{.}\) Since \(\C\) itself is a \(2\)-dimensional \(\R\)-vector space, we must have \(\im \phi=\C\text{.}\)
🔗
🔗
🔗

Example 2.8.16. Field of cardinality 25.

Construct an explicit field of cardinality \(25\)
🔗
Solution.
Consider the polynomial ring \(\F_5[x]\text{.}\) Any quotient of the form \(R=\F_5[x]/(x^2+ax+b)\) is an \(\F_5\)-algebra that is of dimension 2 as an \(\F_5\)-vector space. As a result, any such ring \(R\) satisfies \(\abs{R}=5^2=25\text{.}\) To produce a field, we simply must pick an irreducible quadratic polynomial \(f(x)=x^2+ax+b\text{;}\) and according to Remark 2.8.13, this is equivalent to picking \(f\) so that it has no roots in \(\F_5\text{.}\) Since \(\F_5\) only has 5 elements, it is easy to verify whether a given polynomial has a root in \(\F_5\) or not. Consider \(f(x)=x^2+1\text{,}\) for example. We simply need to compute a table of values
\begin{align} f(0) \amp = 1 \amp f(1)\amp = 2 \amp f(2) \amp =5 =0\tag{2.8.3}\\ f(3) \amp = 0 \amp f(4)\amp =2\tag{2.8.4} \end{align}
to see that \(f\) has two roots in \(\F_5\) (\(x=2\) and \(x=3\)), which corresponds to the factorization \(x^2+1=(x-2)(x-3)\) in \(\F_5[x]\text{.}\) Thus \(x^2+1\) is not irreducible, and the corresponding quotient \(\F_5[x]/(x^2+1)\) is not a field. Indeed, from the factorization we see that \(\alpha=\overline{x}-2\) and \(\beta=\overline{x}-3\) are nonzero elements of \(\F_5[x]/(x^2+1)\) satisfying \(\alpha\beta=0\text{.}\) Thus \(\F_5[x]/(x^2+1)\) is not even an integral domain! (We will see in the next section that \(\F_5[x]/(x^2+1)\cong \F_5\times \F_5\text{.}\))
🔗
Similar computations show that \(f(x)=x^2+2\) has no roots in \(\F_5\) and hence is irreducible. Thus \(F=\F_5[x]/(x^2+2)\) is a field of cardinality \(25\text{.}\) Concretetely, since \(\overline{x}^2=-2=3\) in \(F\text{,}\) we have
\begin{align*} (a+b\overline{x})(c+d\overline{x}) \amp = ac+3bd+(ad+bc)\overline{x} \end{align*}
for all \(a,b,c,d\in \F_5\text{.}\) From this formula, it is easy to see that any nonzero element \(\alpha=a+b\overline{x}\in F\) has inverse
\begin{align*} \alpha^{-1} \amp = (a^2+3b^2)^{-1}(a-b\overline{x})\text{.} \end{align*}
🔗
🔗
🔗

Remark 2.8.17. Finite fields.

It turns out that there are exactly \(\frac{5^2-5}{2}=10\) irreducible polynomials of the form \(f(x)=x^2+ax+b\) in \(\F_5[x]\text{.}\) Each of the corresponding quotients \(\F_5[x]/(f)\) is thus a field of cardinality \(25\text{.}\) Miraculously, these fields are all isomorphic! In fact, as we will prove in the next quarter, given any prime power \(p^n\) there is exactly one field (up to isomorphism) of cardinality \(p^n\text{.}\)
🔗
🔗
We end this section with a fundamental result bounding the number of distinct roots of a polynomial over a field by its domain. This may look familiar to you from your mathematical youth. The corollary that follows, however, should come as more of a surprise.
🔗

Definition 2.8.18. Root of a polynomial.

Let \(R\) be a nonzero commutative ring, and let \(f\in R[x]\) be a polynomial. A root of \(f\) in \(R\) is an element \(r\in R\) satisfying \(f(r)=0\text{.}\)
🔗
More generally, let \(S\) be a commutative \(R\)-algebra with defining homomorphism \(\phi\colon R\rightarrow S\text{.}\) Given \(f(x)=\anpoly\text{,}\) write \(f^\phi(x)=\phi(a_n)x^n+\phi(a_{n-1})x^{n-1}+\cdots \phi(a_1)x+\phi(a_0)\text{:}\) i.e., \(f^\phi\) is the result of applying \(\phi\) to the coefficients of \(f\text{.}\) A root of \(f\) in \(S\) is an element \(s\in S\) satisfying \(f^\phi(s)=0\text{.}\)
🔗
🔗

Proof.

  1. Fix any \(a\in F\text{,}\) and let \(f(x)=q(x)(x-a)+r(x)\) be an instance of the division algorithm applied to \(f\) and \((x-a)\text{,}\) so that \(r(x)=0\) or \(\deg r=0\text{.}\) We have
    \begin{align*} f(a)=0 \amp \iff q(a)(a-a)+r(a)=0 \\ \amp \iff r(a)=0\\ \amp \iff r=0 \amp (\deg r=0\implies r(x)=c)\\ \amp \iff (x-a)\mid f(x)\text{.} \end{align*}
    🔗
    🔗
  2. By induction on \(n=\deg f\text{.}\)
    🔗
    Base case: \(n=0\text{.}\) In this case \(f(x)=c\) is a nonzero constant polynomial. Since \(c\ne 0\text{,}\) clearly \(f(a)\ne 0\) for all \(a\in F\text{,}\) and thus \(f\) has exactly \(0\) distinct roots.
    🔗
    Induction step: let \(n\geq 1\) and assume the claim holds for all nonzero polynomials of degree less than \(n\text{.}\) If \(f\) has no roots in \(F\text{,}\) then the condition is satisfied and we are done. Otherwise, let \(a\) be a root of \(f\text{.}\) By (1) we can write \(f(x)=(x-a)g(x)\) for some \(g\in F[x]\text{.}\) Since \(n=\deg f=\deg(x-a)+\deg g\text{,}\) we see that \(\deg g=n-1\text{.}\) Let \(a_1,a_2,\dots, a_r\) be the distinct roots of \(g\text{.}\) By induction, we have \(r\leq n-1\text{.}\) We claim that \(X=\{a,a_1,\dots, a_r\}\) are the distinct roots of \(f\text{.}\) It is clear that \(f(b)=0\) for all \(b\in X\text{.}\) Conversely, assume \(f(b)=0\) for some \(b\in F\text{.}\) By (1) we have \((x-b)\mid (x-a)g(x)\text{.}\) Since \(x-a\) is irreducible, it is prime, and thus \((x-b)\mid (x-a)\) or \((x-b)\mid g(x)\text{.}\) In the first case, we have \(b-a=0\text{,}\) again by (1), in which case \(b=a\text{.}\) In the second case, \(g(b)=0\text{,}\) and \(b\in \{a_1,a_2,\dots, a_r\}\text{.}\) In both cases we have \(b\in X\text{,}\) as desired.
    🔗
    Thus \(X\) is the set of all roots of \(f\text{.}\) Since \(\abs{X}\leq r+1\leq n-1+1=n\text{,}\) we see that \(f\) has at most \(n\) distinct roots.
    🔗
    🔗
🔗
🔗

Proof.

Let \(G\) be a subgroup of \(F^*\) of cardinality \(n< \infty\text{.}\) Since \(G\) is a finite abelian group, the invariant factor version of the structure theorem for finite abelian groups implies that
\begin{align*} G \amp \cong C_{n_1}\times C_{n_2}\times \cdots \times C_{n_r} \end{align*}
where the \(n_k\) are positive integers satisfying \(n_k\mid n_{k+1}\) for all \(1\leq k\leq r-1\text{,}\) and \(C_{n_k}=\angvec{\alpha_k}\) is a cyclic group of cardinality \(n_k\text{.}\) (We are using multiplicative notation, since \(G\) is a subgroup of the multiplicative group of units.) Since \(n_k\mid n_r\) for all \(k\text{,}\) it follows that all elements \(\alpha\in G\) satisfy \(\alpha^{n_r}=1\text{.}\) Put another way, the polynomial \(f(x)=x^{n_r}-1\) has at least \(n=\abs{G}\) distinct roots. But in general, a nonzero polynomial \(g\in F[x]\) has at most \(\deg g\) distinct roots in \(F\text{.}\) (Why? Using the division algorithm, we have \(g(a)=0\) for some \(a\in F\) if and only if \(g(x)=(x-a)h(x)\text{,}\) where \(\deg h=\deg g -1\text{.}\) The claim now follows easily by induction of \(\deg g\text{.}\) ) Thus on the one hand, \(f(x)=x^{n_r}-1\) has at most \(n_r\) distinct roots, and on the other hand, it has at least \(n=\abs{G}\) distinct roots. It follows that \(n\leq n_r\text{.}\) But since \(n=\prod_{k=1}^r n_k\text{,}\) we have \(n_r\mid n\text{,}\) and hence \(n_r\leq n\text{.}\) It follows that \(n_r=n\) and \(G\cong C_{n_r}\) is cyclic, as claimed.
🔗
🔗
🔗
🔗
PrevTopNext