Classical Algebra (Math 326)
Solutions for Assignment No. 5

Friday, December 5, 2008

1. Find the monic greatest common divisor over the finite field ${\mathbf{F}}_5$ of the two polynomials $$x^4-1\text{and}{x}^4+3x^2+1\text{.}$$

   Response: Use the Euclidean Algorithm. Here are the computations (coefficents in ${\mathbf{F}}_5$): $$\begin{array}{ccc}\hfill \text{stage}\hfill & \hfill \text{remainder}\hfill & \hfill \text{quotient}\hfill \\ \hfill -1\hfill & \hfill x^4+3x^2+1\hfill & \hfill \hfill \\ \hfill 0\hfill & \hfill x^4-1\hfill & \hfill \hfill \\ \hfill 1\hfill & \hfill 3x^2+2\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 0\hfill & \hfill 2x^2+2\hfill \end{array}$$ This computation shows that $3x^2+2=3x^2-3=3\left(x^2-1\right)$ is a greatest common divisor. Of course, $3$, as a non-zero constant, is a unit. The monic greatest common divisor is $x^2-1$.

2. The monic greatest common divisor of the polynomials $$f\left(x\right)=x^5-x-1\text{and}g\left(x\right)=x^3+x+1,$$ regarded as polynomials with rational coefficients, is the constant polynomial $1$. Express $1$ as a polynomial linear combination of $f$ and $g$. (Be sure to verify the correctness of your answer by expanding the linear combination.)

   Response: $$\begin{array}{ccccc}\hfill \text{stage}\hfill & \hfill \text{remainder}\hfill & \hfill \text{quotient}\hfill & \hfill \text{vector-1}\hfill & \hfill \text{vector-2}\hfill \\ \hfill -1\hfill & \hfill x^5-x-1\hfill & \hfill \hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill x^3+x+1\hfill & \hfill \hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -x^2\hfill & \hfill x^2-1\hfill & \hfill 1\hfill & \hfill -x^2+1\hfill \\ \hfill 2\hfill & \hfill x+1\hfill & \hfill -x\hfill & \hfill x\hfill & \hfill -x^3+x+1\hfill \\ \hfill 3\hfill & \hfill -1\hfill & \hfill -x+1\hfill & \hfill x^2-x+1\hfill & \hfill -x^4+x^3\hfill \end{array}$$ Hence, $$1=\left(-x^2+x-1\right)\left(x^5-x-1\right)+\left(x^4-x^3\right)\left(x^3+x+1\right)\text{.}$$

3. Find the order of the congruence class of the polynomial $f\left(x\right)$ modulo the polynomial $m\left(x\right)$ when the field of coefficents is ${\mathbf{F}}_p$ in the following cases:

   (a) $f\left(x\right)=x$, $m\left(x\right)=x^2+1$, and $p=7.$ Ans. $4$ (b) $f\left(x\right)=x$, $m\left(x\right)=x^2-x+2$, and $p=5.$ Ans. $24$ (c) $f\left(x\right)=x-1$, $m\left(x\right)=x^2-x+5$, and $p=7.$ Ans. $6$

4. Find a polynomial $f\left(t\right)$ in ${\mathbf{F}}_5\left[t\right]$ whose congruence class modulo $m\left(t\right)$ is a primitive element for the field ${\mathbf{F}}_5\left[t\right]⁄m\left(t\right){\mathbf{F}}_5\left[t\right]$ when $m\left(t\right)=t^2-t+2$.

   Response: The statement of the problem asserts that the given ring of congruence classes is a field. (This is true because $t^2-t+2$ is irreducible over ${\mathbf{F}}_5$.) Because the polynomial modulus has degree $2$ the number of elements in the field is $25$, and the number of units in the field is $24$. Hence, a primitive element is an element of order $24$. Part (b) in the previous problem shows that $\left[x\right]$ is a primitive element. Since the number of primtive elements is $\phi \left(24\right)=8$, there are $7$ other possibilities.

5. Write a proof of the following proposition: If $F$ is a field and $f\left(t\right)$ is in the ring $F\left[t\right]$ of polynomials with coefficients in $F$, then the polynomial $t$ and the polynomial $f\left(t\right)$ have no (non-constant) common factor if and only if $f\left(0\right)\ne 0$.

   Response: Since $t$ is irreducible, its only monic factors are $1$ and itself. So $f\left(t\right)$ and $t$ have a non-constant factor if and only if $t$ is a common factor, i.e., if and only if $t$ divides $f\left(t\right)$. By the “factor theorem” $t$ divides $f\left(t\right)$ if and only if $f\left(0\right)=0$. So $f\left(t\right)$ and $t$ have a non-constant common factor if and only if $f\left(0\right)=0$, and, therefore, have no non-constant factor if and only if $f\left(0\right)\ne 0$.

6. ${\mathbf{F}}_4$ is defined to be the field ${\mathbf{F}}_2\left[t\right]⁄\left(t^2+t+1\right){\mathbf{F}}_2\left[t\right]$.

   1. How many congruence classes are there of polynomials in ${\mathbf{F}}_4\left[x\right]$ modulo the polynomial $x^3+x^2+1$?

      Response: Every polynomial in ${\mathbf{F}}_4\left[x\right]$ is congruent modulo a cubic polynomial to a unique polynomial of degree at most $2$. Such a polynomial has $3$ coefficients with $4$ possibilities for each. Hence, the number of congruence classes modulo $x^3+x^2+1$ is $4^3=64$.

   2. Explain why the polynomial $x^3+x^2+1$ is irreducible over ${\mathbf{F}}_4$.

      Response: If a cubic is reducible, it must have at least one linear factor, and, therefore, at least one root in ${\mathbf{F}}_4$. Clearly, $0$ and $1$ are not roots of $x^3+x^2+1$. In ${\mathbf{F}}_4$ let $\alpha =t$ and $\beta =t+1$ (the congruence classes of the only two polynomials of degree $1$ in ${\mathbf{F}}_2\left[t\right]$). Then ${\alpha }^2+\alpha +1=0$ or ${\alpha }^2=\alpha +1=\beta$. Then one sees that ${\alpha }^3=\alpha ·{\alpha }^2=\alpha \left(\alpha +1\right)={\alpha }^2+\alpha =1$. Moreover, ${\beta }^2={\left({\alpha }^2\right)}^2={\alpha }^4=\alpha ·{\alpha }^3=\alpha$; hence, ${\beta }^3=\beta ·{\beta }^2=\beta \alpha =\left(\alpha +1\right)\alpha ={\alpha }^2+\alpha =1$. So $x^3+x^2+1$ has no root among the $4$ elements of ${\mathbf{F}}_4$.

   3. Find a primitive element for the ring ${\mathbf{F}}_4\left[x\right]⁄\left(x^3+x^2+1\right){\mathbf{F}}_4\left[x\right]$ of congruence classes.

      Response: Of course, $x^3+x^2+1$ is irreducible over ${\mathbf{F}}_2$ as well as over ${\mathbf{F}}_4$ and ${\mathbf{F}}_2\left[x\right]⁄\left(x^3+x^2+1\right)\cong {\mathbf{F}}_8$ is a field with $8$ elements. Each of the non-zero elements of ${\mathbf{F}}_8$, which are given by non-zero polynomials of degree at most $2$ with coefficients in ${\mathbf{F}}_2$, must have order $1$ or $7$, and, therefore, none of them could be primitive for the field ${\mathbf{F}}_{64}$. So a candidate must have at least one coefficient in ${\mathbf{F}}_4$ that is not in ${\mathbf{F}}_2$. Since there are $63=7·9$ non-zero elements and every element must have order dividing $63$, one sees that for an element to be primitive, it is sufficient that its $9$th and $21$st powers are not $1$. If one tries $x+\alpha$ as a first candidate, then one finds that ${\left(x+\alpha \right)}^9\equiv x^2+x+1$ (an element of ${\mathbf{F}}_8$) and ${\left(x+\alpha \right)}^{21}\equiv \beta$ (an element of ${\mathbf{F}}_4$). Hence, $x+\alpha$ is primitive.