Define $f(x) = x^2 + x + 1 \in \mathbb{Z}_2[x]$. Write down all elements of $\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$ and prove that your list is complete

Question

Define $f(x) = x^2 + x + 1 \in \mathbb{Z}_2[x]$. Write down all elements of $\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$ and prove that your list is complete.

A hint I was given to do this was the following

$$\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x] = \{g(x) + f(x) \mathbb{Z}_2[x] \ | \ g(x) \in \mathbb{Z}_2[x]\}= \{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\}$$

writing down all of the elements afterwords is trivial, but I want to prove the above equivalences and I'm not sure how to go about doing so.

For example I don't see how some polynomial like $x^{4844} + x^{384} + x^1 + 1 \in \mathbb{Z}_2[x]$ can be written in the form $ax + b$ where $a, b \in \mathbb{Z}_2$

Answer 1

I will prove the following:

$$\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x] = \{g(x) + f(x) \mathbb{Z}_2[x] \ | \ g(x) \in \mathbb{Z}_2[x]\} = \{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\}$$

Proof: By definition we have $$\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x] = \{g(x) + f(x) \mathbb{Z}_2[x] \ | \ g(x) \in \mathbb{Z}_2[x]\}$$

Then trivially we have $$\{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\} \subseteq \mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$$

We now prove the converse. Pick $\alpha \in \mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$, then $\alpha = g(x) + f(x)\mathbb{Z}_2[x]$ for some $g(x) \in \mathbb{Z}_2[x]$. Now by the polynomial division theorem there exists $q(x), r(x) \in \mathbb{Z}_2[x]$ such that $g(x) = f(x) \cdot q(x) + r(x)$ and we have that $r(x) = 0_{\mathbb{Z}_2[x]}$ or $\partial(r(x)) < \partial(f(x)) = \partial(x^2 + x + 1) = 2$.

Now if $r(x) = 0_{\mathbb{Z}_2[x]}$ then $\alpha = (f(x) \cdot q(x)) + f(x)\mathbb{Z}_2[x]$

If $\partial(r(x)) = 0$ then we may abbreviate $r(x)$ as $r(x) = r_0$ for some $r_0 \in \mathbb{Z}_2$ and we'd have $\alpha = (f(x) \cdot q(x) + r_0) + f(x)\mathbb{Z}_2[x] = (r_0 + f(x) \cdot q(x)) + f(x)\mathbb{Z}_2[x]$ (by commutativity of the polynomial ring $\mathbb{Z}_2[x]$)

If $\partial(r(x)) = 1 < 2$ then we may abbreviate $r(x)$ as $r(x) = ax + b$ where $a, b \in \mathbb{Z}_2$ and we'd have $$\alpha = (f(x) \cdot q(x) + r(x)) + f(x)\mathbb{Z}_2[x] = (r(x) + f(x) \cdot q(x)) + f(x)\mathbb{Z}_[x] = ((ax + b) + f(x) \cdot q(x)) + \mathbb{Z}_2[x].$$

(Note that I've just used some of the parenthesis above for clarity)

Observe that in the last case when $\partial(r(x)) = 1$ if we let $a = b = 0_{\mathbb{Z}_2}$, then $r(x) = 0_{\mathbb{Z}_2[x]}$ and we obtain the first case. Similarly if we let $a = 0_{\mathbb{Z}_2}$ then we obtain the second case when $\partial(r(x)) = 0$. So the first two cases are special cases of the third case when $\partial(r(x)) = 1$.

So without loss of generality we may assume that $\alpha = ((ax + b) + f(x) \cdot q(x)) + \mathbb{Z}_2[x]$

We now claim that $(ax + b) + f(x)\mathbb{Z}_2[x] = ((ax + b) + f(x) \cdot q(x)) + f(x)\mathbb{Z}_2[x]$. To prove this claim recall that from group theory that if we have two left cosets, $a+H$ and $b+H$ then $a+H = b+H \iff -a + b \in H$.

Note now that $$-(ax + b) + (ax+b) + f(x)\cdot q(x) = f(x) \cdot q(x) \in f(x)\mathbb{Z}_2[x]$$

and thus by the logical equivalence we have proven our claim that $(ax + b) + f(x)\mathbb{Z}_2[x] = ((ax + b) + f(x) \cdot q(x)) + f(x)\mathbb{Z}_2[x]$, hence finally we can conclude that $$\alpha = (ax + b) + f(x)\mathbb{Z}_2[x] \in \{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\}$$ proving that

$$\{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\} \supseteq \mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x]$$

and thus that $$\mathbb{Z}_2[x]/f(x)\mathbb{Z}_2[x] = \{(ax + b ) + f(x)\mathbb{Z}_2[x] \ | \ a, b \in \mathbb{Z}_2\}$$ as desired. $\square$

Answer 2

Hint:

Euclidean division in $\;\mathbf Z_2[x]$. What is the condition on the degree of the remainder?

Answer 3

The polynomial is irreducible, so the quotient ring is a field. If $u$ denotes the image of $x$ in the quotient ring, then the elements are $$ 0,\quad 1,\quad u,\quad 1+u $$ How do you write the image of $x^{4844} + x^{384} + x + 1$? It will be $u^{4884}+u^{384}+u+1$. Note that $u^2=u+1$, so $u^3=u(u+1)=u^2+u=1$.

Thus $u^{4884}=(u^{3})^{1626}=1$; similarly, $u^{384}=(u^3)^{126}=1$; therefore $$ u^{4884}+u^{384}+u+1=1+1+u+1=u+1 $$ The same for any polynomial: just reduce the exponents modulo $3$ and then apply the relation $u^2=u+1$.

By the way, proving $u^3=1$ is not actually needed, because the group of nonzero elements under multiplication has order $3$.