Polynomial division without a remainder

161 Views Asked by At

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

2

There are 2 best solutions below

1
On BEST ANSWER

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

0
On

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