A divisibility problem in GF(3m+1) The following is a problem about polynomials over finite fields I am trying to solve.
The problem:
Let $p$ be a prime of the form $p=3m+1.$
I want to prove that $p(x)=(x+1)^{2m+1}+(x+1)^{m+1}+x+1$ is divisible by $q(x)=x^m-1$ in $GF(p)[x]$ if and only if $p=7$ or $p=13.$
The standard division algorithm and a trivial change of variable allow us to deduce that
$$((x+1)^{2m+1}+(x+1)^{m+1}+x+1)((x+1)^m-1)=(x+1)^{3m+1}-(x+1)=x^{3m+1}-x=(x^{2m+1}+x^{m+1}+x)(x^m-1).$$
Hence both the polynomials $p$ and $q$ divide $x^{p}-x$ and hence they are products of distinct monic factors of degree one. But how can I prove that the only two cases in which all the factors of $q$ appear also in $p$ are when $p=7$ or 13?
 A: The claim follows from the Hasse-Weil bound on the number of points on an elliptic curve over $GF(p)$.
I rename the first polynomial to $r(x)=(x+1)^{2m+1}+(x+1)^{m+1}+(x+1)$ for I don't want to overload the symbol $p$.
We know that the multiplicative group $GF(p)^*$ of the prime field is cyclic of order $3m$. Thus there exists a primitive third root of unity $\omega$, and the subset $G=\{1,\omega,\omega^2\}$ is a cyclic subgroup. We take note of the fact that $\omega$ and $\omega^2$ are the roots of $x^2+x+1$.
Furthermore, for all $a\in GF(p),a\neq0$, we have $a^m\in G$. Cyclicity of $GF(p)^*$ further implies that $a\in GF(p)^*$ is a cube, $a=b^3, b\in GF(p)$, if and only if $a^m=1$. Consequently $a\neq0$ is a non-cube iff $a^m\in\{\omega,\omega^2\}$. Or, equivalently, $a^{2m}+a^m+1=0$. From the rewriting
$$r(x-1)=x(x^{2m}+x^m+1)$$
it thus follows that:

An element $a\in GF(p)$ is a zero of $q(x)$ iff $a$ is a non-zero cube. And an element $a\in GF(p)$ is a zero of $r(x)$, iff $a=-1$ or $a+1$ is a non-cube.

Then consider the curve $E$ defined over $GF(p)$ by the equation
$$x^3=y^3+1.$$
The curve $E$ is elliptic. It has three points on the line at infinity with
homogeneous coordinates $[1:g:0], g\in G$. Similarly, it has three points with $x=0$ and three points with $y=0$.
The Hasse-Weil bound says that altogether there are at least
$$
L(p):=p+1-2\sqrt p
$$
points on the projective version of the curve $E$. The crux is that if $p\ge19$,
then $L(p)\ge L(19)\approx 11.28>9$.

If $p\ge19$ then there exists elements $x,y\in GF(p)$ such that neither is zero and $x^3=y^3+1$.

The claim of the question follows from combining the two highlighted results. Let $(x,y)$ be a solution to $x^3=y^3+1$ whose existence is implied by the latter result.

*

*Because $y^3$ is a non-zero cube, we have $q(y^3)=0$.

*Because $y^3+1=x^3$ is a non-zero cube, we have $r(y^3)\neq0$.

Therefore we can conclude that for all $p\ge19$ we have $q(x)\nmid r(x)$.

It is easy to check that when $x,y\in GF(p)$, $p=7$ or $13$, the equation $x^3=y^3+1$ implies $x=0$ or $y=0$. In $GF(7)$ the cubes are $-1,0,1$, and in $GF(13)$ the cubes are $0,1,5,-5=8$ and $-1=12$. Therefore over these fields we do have $q(x)\mid r(x)$.
