1

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

Jean Marie
  • 81,803
nrofis
  • 210
  • 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 09: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 09:32
  • @JeanMarie, sorry, my mistake... It should be Non Zero remainder – nrofis Jan 25 '18 at 09:36
  • OK. A little detail : remAinder with an "A". – Jean Marie Jan 25 '18 at 09:38
  • Oops.. fixed :) – nrofis Jan 25 '18 at 09:41
  • It's evidently not a mathematical limitation ; it's a hardware or software limitation when computations are done on 2 bytes. – Jean Marie Jan 25 '18 at 09:42
  • Maybe, but I am not so sure, since they are not talking about computers limitations in this section... This is the section that explains what is CRC. – nrofis Jan 25 '18 at 09:47
  • 2
    CRC is a technique to detect errors in binary sequence that uses polynomial division for doing that. – nrofis Jan 25 '18 at 10:05
  • 1
    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
  • Accorginf to GAP, the galois group is actually $S_{15}$, so the claim is correct for all $k\ge 1$ – Peter Jan 25 '18 at 10:23
  • I have found the online version of the book. The link is in the question and it wrote in the first paragraph of page 214 – nrofis Jan 25 '18 at 10:25
  • I have taken the liberty to make your text more fluid. [I wish you will consider it as normal. Personaly, I like when others make comments on my way of writing, it helps to improve one's level in English in particular]. – Jean Marie Jan 26 '18 at 09:16
  • @JeanMarie Thanks, that is fine :) – nrofis Feb 02 '18 at 09:07

2 Answers2

1

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

lhf
  • 216,483
  • 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
1

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

Jyrki Lahtonen
  • 133,153