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