Math 361, Spring 2021, Assignment 10

Carefully define the following terms, and give one example and one non-example of each:

1. $f\%m$ (where $f$ is a polynomial with coefficients in some field $F$, and $m$ is a non-zero polynomial with coefficients in $F$).
2. Standard representative (of an element of $F[x]/\left\langle m\right\rangle$).
3. Standard generator (of $F[x]/\left\langle m\right\rangle$; usually this is denoted by $\alpha$).

Carefully state the following theorems (you do not need to prove them):

1. Theorem concerning unique representation of elements of $F[x]/\left\langle m\right\rangle$.
2. Theorem concerning $m(\alpha)$ (where $\alpha$ is the standard generator of $F[x]/\left\langle m\right\rangle$).

Carefully describe the following procedures:

1. Procedure to calculate the standard representation of the product $(f+\left\langle m\right\rangle)(g+\left\langle m\right\rangle)$ (i.e. the "machine implementation" of multiplication in $F[x]/\left\langle m\right\rangle$).
2. Procedure to rewrite "high" powers of the standard generator $\alpha$ in terms of lower powers, using the theorem concerning $m(\alpha)$ (i.e. the "human implementation" of multiplication in $F[x]/\left\langle m\right\rangle)$).

Solve the following problems:

1. Let $GF(8)$ denote the quotient ring $\mathbb{Z}_2[x]/\left\langle x^3+x+1\right\rangle$. List the elements of $GF(8)$. Be sure to list each element only once. (You will probably find it more pleasant to write them in terms of the standard generator $\alpha$ rather than using coset notation.)
2. Working in $GF(8)$, compute the sum $(1+\alpha^2)+(1+\alpha)$.
3. Using the "machine implementation" of multiplication in $GF(8)$, compute the product $(1+\alpha^2)(1+\alpha)$. Be sure to write your answer in its standard representation.
4. Working in $GF(8)$, find a formula for $\alpha^3$ in terms of lower powers of $\alpha$. (Hint: use the theorem regarding $m(\alpha)$.)
5. Use the formula you found above to compute the standard representations of $\alpha^4, \alpha^5,$ $\alpha^6,$ and $\alpha^7$.
6. Redo your calculation of $(1+\alpha^2)(1+\alpha)$, this time avoiding the "machine implementation" in favor of the formula you found above for $\alpha^3$. Verify that you obtain the same answer.
7. Suppose $m\in\mathbb{Z}_p[x]$ is a polynomial of degree $d$. Compute the cardinality of the ring $\mathbb{Z}_p[x]/\left\langle m\right\rangle$. (Hint: use the theorem on unique representation of elements. How many choices are there for each coefficient, and how many coefficients are there?)
8. Verify that the formula you found above correctly predicts the number of elements of $GF(8)$.

--------------------End of assignment--------------------