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?

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$? — , Oct 21 '18 at 23:48
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$. — , 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 01:04

Robert Lewis · Accepted Answer · 2018-10-22T03:18:32.850

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 00:50

score 2 · Answer 2 · answered Oct 22 '18 at 00:50

2

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

answered Oct 22 '18 at 00:50

Bill Dubuque

272,048

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

score 1 · Answer 3 · answered Oct 22 '18 at 00:04

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.

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

3 Answers3