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

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?

• For the sake of clarity, is $K=\Bbb F_2[X]/(X^3+X+1)$, where $\Bbb F_q$ stands for the field of $q$ elements, an accurate description of your $K$? – Saucy O'Path Oct 21 '18 at 23:48
• What does $\Bbb Z/\Bbb Z[X]$ denote? – Bernard Oct 21 '18 at 23:53
• To be precise, that's quite notation-cluttered, and there should be more parenthesis to disambiguate several non-associative occurrences of "$/$". Also, you are presumably missing a $2$. – Saucy O'Path Oct 21 '18 at 23:54
• yes you're right it's missing a 2 $\mathbb{Z}$/2$\mathbb{Z}$[X]/(d)$\mathbb{Z}$/2$\mathbb{Z}$[X] is the correct formulation. – Wallname Oct 21 '18 at 23:59
• Hint  Use repeated squaring to compute $\,\large x^7\bmod x^3\!+\!x\!+\!1.\$ See my answer for the trivial one-line computation. – Bill Dubuque Oct 22 '18 at 1:04

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}$$

• No need to compute the quotient, e.g. see my one-line answer. – Bill Dubuque Oct 22 '18 at 0:50

$$\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

• We used $\ \large {-}1\equiv 1\$ (by $\,\large 2\equiv 0)\,$ several times above. – Bill Dubuque Oct 22 '18 at 0:59
• Quite clever${}$! – Bernard Oct 22 '18 at 8:07

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.