# Polynomial division without a remainder

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

• 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. – Toby Mak Jan 25 '18 at 9:27
• 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 – nrofis Jan 25 '18 at 9:32
• @JeanMarie, sorry, my mistake... It should be Non Zero remainder – nrofis Jan 25 '18 at 9:36
• [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 – nrofis Jan 25 '18 at 10:05
• 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. – 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}$.

• 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)$. – 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$.