For which $p$ and $q$ polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $F_p[x]$? It easy to prove that polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $\mathbb{Q}[x]$ if $(q,6)=1$, since they don't have a common zero in $\mathbb{C}$, this can be seen geometrically.
My question is to check for which $p,q$ those polynomials are coprime in $F_p[x]$ for prime $p$?
For small values of $p$ and $q$ it is not hard to check this, for example if $p=29$ $q=7$ the polynomials do not have common zeroes and it is not hard to conclude from this that the polynomials are coprime in $F_p[x]$. But for general $p,q$ it is not easy to check if there is a common root.
I would appreciate if someone could help me with this problem, or suggest some related results, literature.
 A: They have a common factor, iff they have a common zero in some extension field of $\Bbb{F}_p$. Assuming $p\nmid q$ the zeros are all simple. The zeros of the first are $\zeta^k, k=0,1,\ldots,q-1$, for a fixed primitive $q$th root of unity $\zeta$. Those of the latter are the elements $-1+\zeta^j, j=0,1,\ldots,q-1$. So we are interested in the possibility
$$
\zeta^k=-1+\zeta^j
$$
for some $k,j$. This happens "often enough". An extremal case is when $q=p^m-1$. Then all the non-zero elements of $\Bbb{F}_{p^m}$ are zeros of the first polynomial, and all the elements $\neq-1$ of $\Bbb{F}_{p^m}$ are zeros of the latter polynomial. Thus their gcd has degree $q-1$.
It is probably possible to say something more useful about this. In particular, when $q$ is relatively small. If you are interested in some specific type of $(p,q)$ pairs, please comment.
But I need to get some shuteye. Hopefully you get more helpful responses while I count sheep. This was a bit too long for a comment, so I post it as an answer instead.
A: When $2^q \equiv 1\  (\operatorname{mod}\ p)$, both polynomials have a root $x=1$.
Also, when $q=2$, we can check that there is a common factor only when $p=3$.  When $q=3$, there is a common factor only when $p=2$.
Putting those cases aside, consider when the cyclotomic polynomial $\Phi_q$ is irreducible modulo $p$.  This occurs when $p$ is a primitive root $(\operatorname{mod}\ q)$.  If $\Phi_q \mid ((x+1)^q-1) $, then $\Phi_q \mid ((x+1)^q-1 - (x^q-1)) = (qx^{q-1}+\cdots + qx+1)$.  This can only happen if ${q\choose k} \equiv q \equiv 1 \ (\operatorname{mod}\ p)$ for all $1\leq k \leq q-1$.
If $p=2$, then $q$ must be a Mersenne prime, which cannot happen for $q>3$ (because we assumed that $2$ is a primitive root).  If $p$ is odd, then, since $q>2$, we have ${q\choose 2} \equiv q\ (\operatorname{mod}\ p)$ gives us $q\equiv 3\ (\operatorname{mod}\ p)$, contradiction.
This is not a complete solution, because $\Phi_q$ may be reducible.  But it gives us a few things to work with:
Common Factor When:


*

*$2^q \equiv 1\  (\operatorname{mod}\ p)$

*$p=2$, $q=3$

*$p=3$, $q=2$


No Common Factor When:


*

*$p\neq 3$, $q=2$

*$p\neq 2$, $q=3$

*$p$ is a primitive root modulo $q$, $q\geq 5$

