1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Saucy O'Path Oct 21 '18 at 23:48
  • $\begingroup$ What does $\Bbb Z/\Bbb Z[X]$ denote? $\endgroup$ – Bernard Oct 21 '18 at 23:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – Saucy O'Path Oct 21 '18 at 23:54
  • $\begingroup$ 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. $\endgroup$ – Wallname Oct 21 '18 at 23:59
  • $\begingroup$ Hint $ $ Use repeated squaring to compute $\,\large x^7\bmod x^3\!+\!x\!+\!1.\ $ See my answer for the trivial one-line computation. $\endgroup$ – Bill Dubuque Oct 22 '18 at 1:04
2
$\begingroup$

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

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

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.