For which $p$ and $q$ polynomials $x^q-1$ and $(x+1)^q-1$ are coprime in $F_p[x]$?

Question

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.

Answer 1

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.

Answer 2

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$