Show that X$^3$+X+1|X$^7$+1

Question

This is a part of the question. Which states Let K= $\mathbb{Z}$/2$\mathbb{Z}$[X]/(d)$\mathbb{Z}$/2$\mathbb{Z}$[X], where
d=X$^3$+X+1 and let a be the class of X modulo d. This is the only part that i do not know how to solve. I have tried calculating the quotient and the remainder but i do not know if it has any meaningful use. And since it has a remainder i cannot find a q(x) that satisfies f(x)=g(x)*q(x). Any tips?

Answer 1

Here are the steps for polynomial long division $\mod 2$, where the notation

$\dfrac{p(X)}{q(X)} \longrightarrow X^k \tag 0$

indicates the quotient of the leading terms is $X^k$:

$\dfrac{X^7 + 1}{X^3 + X + 1} \longrightarrow X^4; \tag 1$

$X^7 + 1 - X^4(X^3 + X + 1) = X^7 + 1 - X^7 - X^5 - X^4 = X^5 + X^4 + 1; \tag 2$

$\dfrac{X^5 + X^4 + 1}{X^3 + X + 1} \longrightarrow X^2; \tag 3$

$X^5 + X^4 + 1 - X^2(X^3 + X + 1) = X^5 + X^4 + 1 - X^5 - X^3 - X^2 = X^4 + X^3 + X^2 + 1; \tag 4$

$\dfrac{X^4 + X^3 + X^2 + 1}{X^3 + X + 1} \longrightarrow X; \tag 5$

$X^4 + X^3 + X^2 + 1 - X(X^3 + X + 1) = X^4 + X^3 + X^2 + 1 - X^4 - X^2 - X = X^3 + X + 1; \tag 6$

$\dfrac{X^3 + X + 1}{X^3 + X + 1} \longrightarrow 1, \tag 7$

and there is clearly no remainder; we gather the terms of the quotient:

$\dfrac{X^7 + 1}{X^3 + X + 1} = X^4 + X^2 + X + 1, \tag 8$

which is easily checked:

$(X^3 + X + 1)( X^4 + X^2 + X + 1)$ $= X^7 + X^5 + X^4 + X^3 + X^5 + X^3 + X^2 + X + X^4 + X^2 + X + 1$ $X^7 + (X^5 + X^5) + (X^4 + X^4) + (X^3 + X^3) +(X^2 + X^2) + (X + X) + 1$ $= X^7 + 1; \tag 9$

thus we see that

$X^3 + X + 1 \mid X^7 + 1. \tag{10}$

Answer 2

I suppose you mean $\;K=(\mathbb{Z}/2\mathbb{Z})[X]/d(\mathbb{Z}/2\mathbb{Z})[X]$.

Hint:

If you have to show that $X^3+X+1\mid X^7+1$ in $(\mathbb{Z}/2\mathbb{Z})[X]$, just perform the Euclidean division of the latter by the former in this polynomial ring. Don't forget that, since we're in characteristic $2$, subtracting is the same as adding. You should find a quotient of $X^4+X^2+X+1$ if I'm not mistaken.

Answer 3

$\bmod 2,\,\color{#c00}{x^{\large 3}\!+\!x\!+1}\!:\,\ x^{\large 7}\!\equiv x(\color{#c00}{x^{\large 3}})^{\large 2}\equiv x(\color{#c00}{x\!+\!1})^{\large 2}\equiv x^{\large 3}\!+x\equiv -1\ \ $ QED