I saw in some book (Page 214) that the polynomial $x^{15}+x^{14}+1$ can divide every polynomial $x^k+1$ for each $k<32768$ with non-zero remainder, without any proof.

I'm just curious to understand why is there the limitation $k<32768$?

The polynomial $x^{15}+x^{14}+1$ has no factor $x^k+1$ for every $k$ ?

I would expect that $x^{15}+x^{14}+1$ divides the polynomial $x^k+1$ with a non-zero remainder for every $k$.

  • $\begingroup$ I'm just guessing, but maybe the proof is related to the fact that $2^{15} = 32768$. It would also help if you name the book that has this claim. $\endgroup$ – Toby Mak Jan 25 '18 at 9:27
  • $\begingroup$ I immediately notice that $2^{15}=32768$ and 15 is the degree of this polynomial. But I don't understand why. The book is not related to mathematics, it called "Computer Networks fifth edition, written by Andrew S. Tanenbaum and David J. Wetherall" in the CRC section $\endgroup$ – nrofis Jan 25 '18 at 9:32
  • $\begingroup$ @JeanMarie, sorry, my mistake... It should be Non Zero remainder $\endgroup$ – nrofis Jan 25 '18 at 9:36
  • 2
    $\begingroup$ [CRC][1] is a technique to detect errors in binary sequence that uses polynomial division for doing that. [1]: en.wikipedia.org/wiki/Cyclic_redundancy_check $\endgroup$ – nrofis Jan 25 '18 at 10:05
  • 1
    $\begingroup$ If the galois group over $\mathbb Q$ of $x^{15}+x^{14}+1$ is $S_{15}$ , (maybe someone can check it), then you are right because a root of $x^{15}+x^{14}+1$ cannot be a root of any polynomial $x^k+1$ because the latter roots can be expressed via radicals. $\endgroup$ – Peter Jan 25 '18 at 10:06

The context of the book is probably finite fields of characteristic $2$.

$x^{15}+x^{14}+1$ is probably irreducible mod $2$.

Therefore, $\mathbb Z_2[X]/(x^{15}+x^{14}+1)$ is $GF(2^{15})$, the finite field of order $2^{15}$. This is the smallest field that contains the roots of $x^{15}+x^{14}+1$.

The roots of $x^k+1$ are in $GF(n)$ with $n< 2^k$.

Thus, $x^k+1$ cannot be divisible by $x^{15}+x^{14}+1$ if $k < 2^{15}$.

However, $x^k+1$ is divisible by $x^{15}+x^{14}+1$ if $k = 2^{15}$.

  • $\begingroup$ We need to prove that this polynomial is primitive to conclude that $k=2^{15}-1$ is the smallest exponent. +1 for the key observation about this being over $GF(2)$. $\endgroup$ – Jyrki Lahtonen Jan 25 '18 at 10:36

It seems very likely to me (I have accumulated a bit of experience :-/) that your question is about divisibility of polynomials in the ring $\Bbb{F}_2[x]$. There we have the following result.

Proposition. If $p(x)\in\Bbb{F}_2[x]$ has constant term equal to $1$, then there exists a positive integer $k$ such that $$p(x)\mid x^k+1.$$

Proof. The quotient ring $\Bbb{F}_2[x]/\langle p(x)\rangle$ is a finite ring (the number of elements is $2^{\deg p(x)}.$ Therefore there exists integers $0<i<j$ such that $x^i$ and $x^j$ are in the same coset modulo $p(x)$. Consequently $p(x)$ is a factor of $x^j-x^i=x^j+x^i$ and therefore also of $x^{j-i}+1$. This last step is where the assumption about the constant term was used.

In many applications (such as CRC-polynomials) we need to find the smallest $k$ such that $p(x)\mid x^k+1$. This is because CRC loses quite a bit of its potency, if the length of the data block exceeds $k$ (it will no longer catch all 2-bit errors).

Assuming that you have ascertained that $f(x)=x^{15}+x^{14}+1$ is irreducible, then we know that the smallest $k$ will be a factor of $32767=2^{15}-1=7\cdot 31\cdot 151$. This is because the zeros of $f(x)$ belong to the field $GF(2^{15})$, and thus are roots of unity of order that is a factor of $32767$.

We also know that because those zeros don't belong to the subfields $GF(2^3)$ or $GF(2^5)$ that the order of the roots of unity cannot be a factor of either $2^3-1=7$ or $2^5-1=31$. But, their order (and hence also the smallest $k$) could be one of $151, 7\cdot31, 7\cdot151,31\cdot151$.

Excluding those possibilities with pencil & paper work is a bit taxing, so I fired up my Mathematica: $$ \begin{aligned} x^{7\cdot31}&\equiv x^{13}+x^{11}+x^{10}+x^8+x^6+x^4+x^3+x+1\pmod{f},\\ x^{7\cdot151}&\equiv x^{14}+x^{11}+x^9+x^8+x^3+x^2+1\pmod{f},\\ x^{31\cdot151}&\equiv x^{13}+x^8+x^7+x^5+1\pmod{f}. \end{aligned} $$ None of those remainders was equal to $1$, so we can conclude that $2^{15}-1$ is the smallest possible $k$. Observe that the remainder of $x^{151}$ cannot be equal to $1$ for in that case the same would hold for both $x^{7\cdot 151}$ and $x^{31\cdot151}$. In other words, when verifying the primitivity of a polynomial it suffices to exclude maximal proper subdivisors of $32767$ as the minimal $k$.


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.