Topics in Algebra, Chapter 3.9
This page covers section 3.9 ("Polynomial Rings"). Throughout, $F$ is a field. ### Topics covered: 3.9 * $F[x]=\{a_0+a_1 x+\cdots a_n x^n\mid n\in\mathbb{N},a_0,\ldots,a_n\in F\}$ is the set of polynomials with coefficients from the field $F$. * Addition, multiplication and equivalence of polynomials are defined in the obvious ways. * **Definition**: The degree of non-zero $f\in F[x]$, ${\rm deg}(f)$, is the coefficient of the highest non-zero power of $x$ in $f$. The degree is not defined for the zero polynomial. * **Lemma 3.9.1**: If $f,g\in F[x]$ are non-zero, then ${\rm deg}(fg)={\rm deg}(f)+{\rm deg}(g)$. * **Corollary**: $F[x]$ is an integral domain. * **Lemma 3.9.2**: Given $f,g\in F[x]$, $g\ne 0$, there exist $r,t\in F[x]$ such that $f(x)=t(x)g(x)+r(x)$ with either $r=0$ or ${\rm deg}(r)<{\rm deg}(g)$. This is the Euclidean algorithm. * **Theorem 3.9.1**: $F[x]$ is a Euclidean ring with ${\rm deg}$ used as norm. The problems below are paraphrased from/inspired by those given in Topics in Algebra by Herstein. The solutions are my own unless otherwise noted. I will generally try, in my solutions, to stick to the development in the text. This means that problems will not be solved using ideas and theorems presented further on in the book. ### Herstein 3.9.1: Find the greatest common divisor in $\mathbb{Q}[x]$ of ### (a) $x^3-6x^2+x+4$ and $x^5-6x+1$. ### (b) $x^2+1$ and $x^6+x^3+x+1$. **(a)** Unlike the exercise on Gaussian integer divisors, polynomial long division takes away any interesting guess work in computing the greatest common divisor (we use the algorithm in problem 3.7.4). The numbers for this particular example work out horrendously, but we find (in the notation of 3.7.4) that $$r_3=-\frac{7730176}{57121}$$ which is a unit in $\mathbb{Q}$, so $x^3-6x^2+x+4$ and $x^5-6x+1$ are coprime in $\mathbb{Q}[x]$. **(b)** In stark contrast to the hideous arithmetic of part (a), we find that $x^2+1$ actually divides $x^6+x^3+x+1$. Specifically, $$x^6+x^3+x+1=(x^4-x^2+x+1)(x^2+1)$$ so their greatest common divisor is $x^2+1$. ### Herstein 3.9.2: ### (a) Show that $x^2+x+1$ is irreducible over $F_2=\mathbb{Z}/2\mathbb{Z}$. ### (b) Show that $x^2+1$ is irreducible over $F_7=\mathbb{Z}/7\mathbb{Z}$. ### (c) Show that $x^3-9$ is irreducible over $F_{31}=\mathbb{Z}/31\mathbb{Z}$. ### (d) Show that $x^3-9$ is reducible over $F_{11}=\mathbb{Z}/11\mathbb{Z}$. **(a)** Suppose that $x^2+x+1=a(x)b(x)$ with $a,b\in F_2[x]$, neither being a constant. Then we must have ${\rm deg}(a)={\rm deg}(b)=1$. Write $a(x)=\alpha x+\beta$ and $b(x)=\gamma x+\delta$, where $\alpha,\beta,\gamma,\delta\in F_2$ can each take only the values $0$ or $1$. Expanding the product, we have $\alpha\gamma=1$ which implies $\alpha=\gamma=1$, and $\beta\delta=1$ implies $\beta=\delta=1$. Then the cross term is $\alpha\delta+\beta\gamma=0\in F_2$, but the coefficient of $x$ is supposed to be $1$. Thus $x^2+x+1$ can not be factored unless one of the factors is a unit, so it is irreducible. **(b)** As before, let us try to write $x^2+1=(\alpha x+\beta)(\gamma x+\delta)$. We find by expanding that $\gamma=\alpha^{-1}$ and $\delta=\beta^{-1}$. In fact, we can factor out $\alpha$ and $\alpha^{-1}$ to get $x^2+1=(x+\alpha^{-1}\beta)(x+\alpha\beta^{-1})$. Equivalently, just call $\alpha\beta^{-1}=\eta$. Then we have $$x^2+1=(x+\eta)(x+\eta^{-1})$$ which has us conclude that $\eta+\eta^{-1}=0$. But then $$1=\eta\eta^{-1}=-\eta^2\mod 7.$$ However, because $7$ is a $4k+3$ prime, this is not possible (problem 3.8.4) and therefore $x^2+1$ is irreducible over $F_7$. Note that this argument fails if we work over other fields such as $\mathbb{Z}/5\mathbb{Z}$. In that case, we have $2^2\equiv-1\mod 5$ and $2^{-1}=3$, so $$(x+2)(x+3)=x^2+5x+6=x^2+1.$$ **(c)** If $x^3-9$ is reducible, then it must have at least one linear factor by simple considerations of degree. We can therefore write a proposed factorization as $$x^3-9=(x+\alpha)(x^2+\beta x+\gamma).$$ The coefficients give conditions $\beta=-\alpha$, $\gamma=-\alpha\beta$ and $\alpha\gamma=-9$. Combining all three, we find that $$\alpha^3=-9=22\mod 31.$$ By brute force we see that this can never happen, so $x^3-9$ is irreducible over $F_{31}$. Alternately, as suggested in this math.stackexchange.com post, we note that $F_{31}^\times$ is a cyclic group of order $30$ so that $\alpha^{30}=1$. Then if $22$ is expressible as a cube, it must be the case that $22^{10}\equiv1\mod 31$. However, we can easily show that $22^{10}\equiv5\mod 31$: first switch back to computing $(-9)^{10}$ because $9$ is smaller and easier to square by hand. We have $9^2=-12$ and then $9^4=144=-11$ and $9^8=121=-3$. Finally, plugging back in, we get $$(-9)^{10}=9^8\cdot9^2=(-3)(-12)=5\mod 31.$$ This shows that $-9$ is not the cube of any number in $F_{31}$, so the polynomial is irreducible. **(d)** The same reasoning as above brings us to the condition $\alpha^3=2\mod 11$. This can be simplified slightly by applying Fermat's little theorem. We can see that $$5=2^4=(\alpha^3)^4=\alpha^{11}\cdot\alpha=\alpha^2\mod 11.$$ From here it can easily be brute forced by hand, and we find that $\alpha=7$ so $\beta=-7$ and $\gamma=5$ constitutes a solution. Specifically, $$x^3-9=(x+7)(x^2-7x+5)$$ over $\mathbb{Z}/11\mathbb{Z}$. It is immaterial whether $x^2-7x+5$ factors further (it doesn't), because the object was simply to show that $x^3-9$ is reducible. ### Herstein 3.9.3: Let $F\subset K$ be two fields and suppose $f,g\in F[x]$ are relatively prime. Show that they are relatively prime in $K[x]$. Because $f$ and $g$ are relatively prime in $F[x]$, there exist $\alpha,\beta\in F[x]$ such that $$\alpha(x)f(x)+\beta(x)g(x)=1$$ for all $x$. The elements $\alpha$ and $\beta$ also belong to $K[x]$, so this identity holds there, too. ### Herstein 3.9.4: Let $F=\mathbb{Z}/11\mathbb{Z}$. ### (a) Prove that $x^2+1$ is irreducible over $F$ and explicitly prove that $F[x]/(x^2+1)$ is a field with $121$ elements. ### (b) Prove that $x^2+x+4$ is irreducible over $F$ and explicitly prove that $F[x]/(x^2+x+4)$ is a field with $121$ elements. ### (c) Prove that $F[x]/(x^2+1)\cong F[x]/(x^2+x+4)$. **(a)** $x^2+1$ is irreducible over $F$ by precisely the same argument as in problem 3.9.2b. Denote the ideal $(x^2+1)$ by $I$. We have defined $$F[x]/I=\{f+I\mid f\in F[x]\},$$ and we see by the Euclidean algorithm that any representative $f\in F[x]$ may be written as $$f(x)=q(x)\cdot(x^2+1)+r(x)$$ with $r=0$ or ${\rm deg}(r)<2$ by the Euclidean algorithm. Hence $f(x)+I=r(x)+I$. We can express $r(x)=\alpha x+\beta$, where $\alpha,\beta\in F$ each have $11$ possible values. Therefore we can enumerate $121$ elements in $F[x]/I$. It is conceivable that there is some overcounting, but if $$\alpha x+\beta+I=\alpha' x+\beta'+I$$ then $x^2+1$ must divide $(\alpha-\alpha')x+(\beta-\beta')$. This is only possible if both coefficients are zero, so $\alpha'=\alpha$ and $\beta'=\beta$ and we must have no duplicates. Therefore there are $121$ elements in $F[x]/I$. To show that $F[x]/I$ is a field, we take the properties of a ring for granted and would just like to show that every element has a multiplicative inverse. That is, we would like to explicitly produce an inverse of the arbitrary element $\alpha x+\beta+I\in F[x]/I$. If $\alpha=0$ and $\beta\ne 0$, then the inverse is $\beta^{-1}+I$; if $\beta=0$ and $\alpha\ne 0$, the inverse is $-\alpha^{-1}x+I$ because $$(\alpha x)(-\alpha^{-1}x)+I=-x^2+I=1-(x^2+1)+I=1+I.$$ Therefore we are left to solve $$(\alpha x+\beta)(\gamma x+\delta)+I=1+I$$ for $\gamma$ and $\delta$, with $\alpha,\beta\ne 0$. Comparing coefficients quickly indicates the forms $\gamma=\eta\alpha^{-1}$ and $\delta=\eta\beta^{-1}$. Then $$1+I=(\alpha x+\beta)(\eta\alpha^{-1}x+\eta\beta^{-1})+I=\eta\left(\alpha\beta^{-1}+\left(\alpha\beta^{-1}\right)^{-1}\right)+I.$$ It will always be possible to solve this if the latter term in parentheses is non-zero, because $\eta$ can be chosen as its inverse. Suppose that, for some $x\in F$, $x+x^{-1}=0$. Then $1=xx^{-1}=-x^2$ or $x^2\equiv-1\mod 11$. This we know to be impossible by problem 3.8.4. Therefore if we take $$\eta=\left(\alpha\beta^{-1}+\left(\alpha\beta^{-1}\right)^{-1}\right)^{-1}$$ then the inverse of $\alpha x+\beta+I$ in $F[x]/I$ is given by $\eta(\alpha^{-1}x+\beta^{-1})+I$ and, consequently, $F[x]/I$ is a field. **(b)** Suppose that $x^2+x+4$ factors in $F[x]$ as $$x^2+x+4=(\alpha x+\beta)(\gamma x+\delta)$$ with $\alpha,\beta,\gamma,\delta\in F$. Then we find $\gamma=\alpha^{-1}$ and $\delta=4\beta^{-1}$ (ignoring the trivial possibilities that $\alpha=0$ or $\beta=0$) and, plugging in and extracting a factor of $1=\alpha\alpha^{-1}$, we see that $$x^2+x+4=(x+\alpha^{-1}\beta)(x+4\alpha\beta^{-1}).$$ The condition on the $x$ coefficient is then $\alpha^{-1}\beta+4\alpha\beta^{-1}=1$ which may be restated as $t+4t^{-1}=1$ for some $t\in F$. If we can show that there is no solution to this last equation, then we have shown that $x^2+x+4$ is irreducible over $F$. Multiply through by $t$ to get $t^2-t+4=0$ or $t^2-t+3=-1$. Now, modulo $11$, we have that $$(t+5)^2=t^2+10t+25=t^2-t+3$$ and we know that $(t+5)^2\equiv-1\mod 11$ is not possible. Therefore the polynomial is irreducible over $F$. Letting $J=(x^2+x+4)$, the Euclidean algorithm argument from part (a) shows that there are exactly $121$ elements in $F[x]/J$. Again, we would like to explicitly produce an inverse of $\alpha x+\beta+J$ in $F[x]/J$. If $\alpha=0$ and $\beta\ne 0$, then the inverse is simply $\beta^{-1}+J$. If $\beta=0$ and $\alpha\ne 0$, then we have $$1+J=(\alpha x)(\gamma x+\delta)+J=\alpha\gamma x^2+\alpha\delta x+J.$$ Write this as $$1+J=\alpha\gamma(x^2+x+4)+\alpha\delta x-\alpha\gamma x-4\alpha\gamma+J=\alpha(\delta-\gamma)x-4\alpha\gamma+J.$$ Then we have $\delta=\gamma$ and $-4\alpha\gamma=1$ modulo $11$. The latter equation is solved by multiplying through by $8\alpha^{-1}$. Thus $$(\alpha x)(8\alpha^{-1}x+8\alpha^{-1})+J=1+J.$$ Finally, we come to the case of $\alpha,\beta\ne 0$. If $(\alpha x+\beta)(\gamma x+\delta)+J=1+J$, then the same trick of adding and subtracting terms gives $$(\alpha\delta+\beta\gamma-\alpha\gamma)x+(\beta\delta-4\alpha\gamma)+J=1+J.$$ Then $\delta=\beta^{-1}+4\alpha\beta^{-1}\gamma$ and so $$0=\alpha\delta+\beta\gamma-\alpha\gamma=\alpha\beta^{-1}-(\alpha-\beta-4\alpha^2\beta^{-1})\gamma.$$ Can $\alpha-\beta-4\alpha^2\beta^{-1}=0$? Multiply through by $\alpha^{-1}$ to put it in the form $$t^2-t-4=0$$ where $t=\beta\alpha^{-1}$. As shown above, this is equivalent to $(t+5)^2=-1$ which is not possible modulo $11$. Hence we can always solve for $$\gamma=\alpha\beta^{-1}(\alpha-\beta-4\alpha^2\beta^{-1})^{-1},$$ so the inverse is constructed and $F[x]/J$ is a field. **(c)** We would like to construct an explicit isomorphism $\phi: F[x]/I\to F[x]/J$. An important first question is whether such a $\phi$ can refer to the coefficients $\alpha$ and $\beta$ of $\alpha x+\beta+I$ in a well-defined way. The answer is yes: if $\alpha x+\beta+I=\alpha' x+\beta'+I$, then $(\alpha-\alpha')x+(\beta-\beta')$ is divisible by $x^2+1$. This is only possible if both coefficients are zero, so $\alpha'=\alpha$ and $\beta'=\beta$. A natural guess for the isomorphism is the simple $\phi(\alpha x+\beta+I)=\alpha x+\beta+J$. A homomorphism must satisfy $\phi(ab)=\phi(a)\phi(b)$ for $a,b\in F[x]/I$. However, we can see, for example, that $$\phi((x+I)^2)=\phi((x^2+1)-1+I)=\phi(-1+I)=-1+J$$ while $$\phi(x+I)^2=x^2+J=(x^2+x+4)-(x+4)+J=-(x+4)+J$$ so this map fails to be a homomorphism. If we work from the restriction that $\phi$ be a homomorphism, we know that $$\phi(\alpha x+\beta+I)=\phi(\alpha+I)\phi(x+I)+\phi(\beta+I).$$ Then the map will be fully determined by computing its action on $1+I$ and $x+I$. We know by problem 3.4.20 that if $\phi$ is an isomorphism then it maps onto $F[x]/J$ and thus $\phi(1+I)=1+J$. From this, it easily follows that $\phi(\alpha+I)=\alpha+J$ for any $\alpha\in F$. For $x+I$, we have $$-1+J=\phi(-1+I)=\phi((x^2+1)-1+I)=\phi(x^2+I)=\phi(x+I)^2.$$ This implies that $\phi(x+I)$ must be an element of $F[x]/J$ which squares to $-1+J=x^2+x+3+J$. Such an element is $x-5+J$, because $$(x-5+J)^2=x^2-10x+25+J=x^2+x+3+J.$$ So we posit that $\phi:F[x]/I\to F[x]/J$ defined by $$\phi(\alpha x+\beta+I)=\alpha x+\beta-5\alpha+J$$ is an isomorphism. The only non-trivial property to check is that $\phi$ respects products. Letting $\alpha,\beta,\gamma,\delta\in F$, we have $$\begin{multline*} \phi((\alpha x+\beta)(\gamma x+\delta)+I)=\phi((\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma)+I)\\ =(\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma-5\alpha\delta-5\beta\gamma)+J \end{multline*}$$ while $$\begin{multline*} \phi(\alpha x+\beta+I)\phi(\gamma x+\delta+I)\\ =\alpha\gamma x^2+(\alpha(\delta-5\gamma)+\gamma(\beta-5\alpha))x+(\beta-5\alpha)(\delta-5\gamma)+J\\ =\alpha\gamma(x^2+x+4)+(\alpha(\delta-5\gamma)+\gamma(\beta-5\alpha)-\alpha\gamma)x\\+(\beta-5\alpha)(\delta-5\gamma)-4\alpha\gamma+J\\ =(\alpha\delta+\beta\gamma)x+(\beta\delta-\alpha\gamma-5\alpha\delta-5\beta\gamma)+J. \end{multline*}$$ Therefore $\phi$ respects the ring product. It is very easy to check that it respects ring addition and that it is injective, and so we have proven that $F[x]/I\cong F[x]/J$. ### Herstein 3.9.5: Letting $F=\mathbb{R}$, show that $F[x]/(x^2+1)\cong\mathbb{C}$ as fields. First we show that $x^2+1$ is irreducible over $F$. Suppose that $x^2+1=(\alpha x+\beta)(\gamma x+\delta)$. Then, comparing coefficients, $\alpha\gamma=1$ and $\beta\delta=1$ imply that $\alpha,\beta\ne 0$, $\gamma=1/\alpha$ and $\delta=1/\beta$. Then the middle coefficient says $0=\alpha\delta+\beta\gamma=\frac{\alpha}{\beta}+\frac{\beta}{\alpha}$. This gives $\alpha^2=-\beta^2$ which in turn implies that $\alpha=\beta=0$, a contradiction. Therefore $x^2+1$ is irreducible over $F$ and lemma 3.9.6 says that $I=(x^2+1)$ is maximal in $F[x]$. Theorem 3.5.1 then says that $F[x]/I$ is a field much like the one studied in problem 3.9.4a. The elements look like $\alpha+\beta x+I$ with $\alpha,\beta\in F$. The obvious choice for a map to $\mathbb{C}$ is $$\phi(\alpha+\beta x+I)=\alpha+i\beta$$ which is well-defined by the comments made in 3.9.4c. One has to be a little careful here: $\alpha x+\beta\mapsto\alpha+i\beta$ (with the $\alpha$ and $\beta$ flipped from the definition above) fails to respect the ring multiplication. With the definition of $\phi$, we have $$\begin{multline} \phi((\alpha+\beta x)(\gamma+\delta x)+I)=\phi(\alpha\gamma-\beta\delta+(\beta\gamma+\alpha\delta)x+I)\\ =\alpha\gamma-\beta\delta+(\beta\gamma+\alpha\delta)i=(\alpha+i\beta)(\gamma+i\delta). \end{multline}$$ The additive property $\phi(a+b)=\phi(a)+\phi(b)$ is very easy to show, so $\phi$ is a homomorphism. It is also trivially surjective because $\alpha+\beta i$ is the image of $\alpha+\beta x+I$, and trivially injective because $\phi(\alpha+\beta x+I)=\phi(\alpha' x+\beta'+I)$ implies $(\alpha-\alpha')+i(\beta-\beta')=0$ or $\alpha'=\alpha$ and $\beta'=\beta$. Therefore, $F[x]/I\cong\mathbb{C}$. ### Herstein 3.9.6*: Let $F=\mathbb{Q}$ and define the formal derivative $f'\in F[x]$ of polynomial $f\in F[x]$ in the usual way. Prove that $f(x)$ is divisible by the square of a non-constant polynomial if and only if $f(x)$ and $f'(x)$ have a greatest common divisor $d(x)$ of positive degree. Note that, over $\mathbb{Q}$, the degree of a polynomial's derivative is exactly one less than the degree of the polynomial. In other fields, this may not be the case. For instance, the derivative of $x^2$ over $\mathbb{Z}/2\mathbb{Z}$ is zero. First suppose that $f\in F[x]$ is divisible by the square of a non-constant polynomial $p\in F[x]$, writing $$f(x)=p(x)^2 q(x).$$ Then the derivative is $f'(x)=2p(x)q(x)p'(x)+p(x)^2 q'(x)$ so that $p\mid f'$. As $p$ is a common divisor, it also divides the greatest common divisor $d$, and so ${\rm deg}(d)\ge{\rm deg}(p)$ as desired. On the other hand, suppose that we know $f(x)$ and $f'(x)$ have a non-trivial greatest common divisor $d(x)$. Factor $d$ into primes as $$d(x)=\pi_1(x)\cdots\pi_N(x)$$ and take any of the primes, say $\pi_1$. We have that $\pi_1$ is a common divisor of $f$ and $f'$, so write $f(x)=\pi_1(x) p(x)$ and $f'(x)=\pi_1(x) q(x)$. We can also compute the derivative by the chain rule, which gives $f'(x)=\pi_1(x)p'(x)+\pi_1'(x)p(x)$. Equating the two representations gives $$(q(x)-p'(x))\pi_1(x)=p(x)\pi_1'(x).$$ Because $\pi_1$ is prime, it divides either $p(x)$ or $\pi_1'(x)$. The latter is impossible, because ${\rm deg}(\pi_1')$ is strictly smaller than ${\rm deg}(\pi_1)$. Therefore $\pi_1\mid p$ and $\pi_1^2\mid f$. ### Herstein 3.9.7: Let $F=\mathbb{Z}/p\mathbb{Z}$ with $p$ prime, and let $f\in F[x]$ be irreducible and have degree $n$. Prove that $F[x]/(f)$ is a field with $p^n$ elements. By lemma 3.9.6, $(f)$ is maximal and, by theorem 3.5.1, $F[x]/(f)$ is a field. A generic element in $F[x]/(f)$ is $g+(f)$ where $g\in F[x]$. By the division algorithm, we can write $$g(x)=q(x)f(x)+r(x)$$ where $r=0$ or ${\rm deg}(r)<{\rm deg}(f)$. Therefore, $g+(f)=r+(f)$ and so we will always be able to identify an equivalence class by a polynomial of degree smaller than $n$. The representative of any equivalence class can be written $$r(x)=a_0+a_1 x+\cdots+a_{n-1}x^{n-1}$$ where $a_i\in F$ for each $i=1,\ldots,n-1$. With $p$ choices for each of the $n$ coefficients, there are at most $p^n$ equivalence classes comprising $F[x]/(f)$. However, there are also no duplicates. Indeed, if $r+(f)=r'+(f)$, then $r-r'$ is divisible by $f$. Because each of $r$ and $r'$ has degree smaller than $n$, so does their difference. The only way for the difference to be divisible by $f$ is if it is zero, i.e. if $r'=r$. Therefore each of the $p^n$ polynomials described above represents a unique equivalence class, and $F[x]/(f)$ has $p^n$ elements.