Are $1+p^3+p^6$ and $1+p^4+p^8$ coprime?

Question

What are the primes $p$ for which $1+p^3+p^6$ and $1+p^4+p^8$ are coprime? I know it is true for $p=2$ and $p=3$ and not true for any $p \equiv 1 \mod 6$. I conjecture that it true for all primes $p \equiv 5 \mod 6$.

Any counterexample $> 10^8$.

This is relevant to OEIS sequence A046685.

Answer 1

Let $p$ be an integer.

Suppose $\gcd(1+p^3+p^6,1+p^4+p^8) = u > 1$. \begin{align*} \text{Then}\;\;&1+p^3+p^6\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&(p^3-1)(p^6+p^3+1)\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&p^9-1\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&p^9\equiv 1\;(\text{mod}\;u)\\[10pt] \text{Similarly}\;\;&1+p^4+p^8\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&(p^4-1)(p^8+p^4+1)\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&p^{12}-1\equiv 0\;(\text{mod}\;u)\\[4pt] \implies\;&p^{12}\equiv 1\;(\text{mod}\;u)\\[10pt] \text{Then}\;\;& \begin{cases} p^{12}\equiv 1\;(\text{mod}\;u)\\[4pt] p^9\equiv 1\;(\text{mod}\;u)\\ \end{cases}\\[4pt] \implies\;&p^3\equiv 1\;(\text{mod}\;u)\\[4pt] \implies\;&p^6\equiv 1\;(\text{mod}\;u)\\[4pt] \implies\;&1+p^3+p^6\equiv 3\;(\text{mod}\;u)\\[4pt] \implies\;&0\equiv 3\;(\text{mod}\;u)\\[4pt] \implies\;&u=3\\[4pt] \implies\;&p^3\equiv 1\;(\text{mod}\;3)\\[4pt] \implies\;&p\equiv 1\;(\text{mod}\;3)\\[4pt] \end{align*}

It follows that $1+p^3+p^6$ and $1+p^4+p^8$ are relatively prime unless $p\equiv 1\;(\text{mod}\;3)$, in which case, their $\gcd$ is $3$.

For the case where $p$ is prime, $p\equiv 1\;(\text{mod}\;3)$ is equivalent to $p\equiv 1\;(\text{mod}\;6)$, hence $1+p^3+p^6$ and $1+p^4+p^8$ are relatively prime unless $p\equiv 1\;(\text{mod}\;6)$, in which case, their $\gcd$ is $3$.

Answer 2

From comments, therefore CW:

$$ \left( x^{8} + x^{4} + 1 \right) $$

$$ \left( x^{6} + x^{3} + 1 \right) $$

$$ \left( x^{8} + x^{4} + 1 \right) = \left( x^{6} + x^{3} + 1 \right) \cdot \color{magenta}{ \left( x^{2} \right) } + \left( - x^{5} + x^{4} - x^{2} + 1 \right) $$ $$ \left( x^{6} + x^{3} + 1 \right) = \left( - x^{5} + x^{4} - x^{2} + 1 \right) \cdot \color{magenta}{ \left( - x - 1 \right) } + \left( x^{4} - x^{2} + x + 2 \right) $$ $$ \left( - x^{5} + x^{4} - x^{2} + 1 \right) = \left( x^{4} - x^{2} + x + 2 \right) \cdot \color{magenta}{ \left( - x + 1 \right) } + \left( - x^{3} + x^{2} + x - 1 \right) $$ $$ \left( x^{4} - x^{2} + x + 2 \right) = \left( - x^{3} + x^{2} + x - 1 \right) \cdot \color{magenta}{ \left( - x - 1 \right) } + \left( x^{2} + x + 1 \right) $$ $$ \left( - x^{3} + x^{2} + x - 1 \right) = \left( x^{2} + x + 1 \right) \cdot \color{magenta}{ \left( - x + 2 \right) } + \left( -3 \right) $$ $$ \left( x^{2} + x + 1 \right) = \left( -3 \right) \cdot \color{magenta}{ \left( \frac{ - x^{2} - x - 1 }{ 3 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( x^{2} \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{2} \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( - x - 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( - x^{3} - x^{2} + 1 \right) }{ \left( - x - 1 \right) } $$ $$ \color{magenta}{ \left( - x + 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{4} - x + 1 \right) }{ \left( x^{2} \right) } $$ $$ \color{magenta}{ \left( - x - 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( - x^{5} - x^{4} - x^{3} \right) }{ \left( - x^{3} - x^{2} - x - 1 \right) } $$ $$ \color{magenta}{ \left( - x + 2 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{6} - x^{5} - 2 x^{3} - x + 1 \right) }{ \left( x^{4} - x^{3} - x - 2 \right) } $$ $$ \color{magenta}{ \left( \frac{ - x^{2} - x - 1 }{ 3 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - x^{8} - x^{4} - 1 }{ 3 } \right) }{ \left( \frac{ - x^{6} - x^{3} - 1 }{ 3 } \right) } $$ $$ \left( x^{8} + x^{4} + 1 \right) \left( \frac{ x^{4} - x^{3} - x - 2 }{ 3 } \right) - \left( x^{6} + x^{3} + 1 \right) \left( \frac{ x^{6} - x^{5} - 2 x^{3} - x + 1 }{ 3 } \right) = \left( -1 \right) $$

Answer 3

This answer is no more than an expansion of the very first comment by Daniel Schepler (since hed did not write it as an answer himself).

Since we are interested in the "pointwise" GCD (greatest common divisor) of $f=x^6+x^3+1$ and $g=x^8+x^4+1$ for particular whole numbers $x$, it is a good idea to start with the GCD within the graded ring $\mathbb{Z}[x]$ of these two polynomials. If we even use the extended Euclidean algorithm, we get a Bézout identity: $$(x^6 - x^5 - 2x^3 - x + 1)(x^6+x^3+1) + (-x^4 + x^3 + x + 2)(x^8+x^4+1)=3$$

See machine-generated answer by Will Jaggy/Community wiki for some details. Can also be found by PARI/GP with gcdext(x^6+x^3+1,x^8+x^4+1) (and multiplying the output by 3 to get rid of fractions).

This Bézout-type identity shows that for any $x\in\mathbb{N}$, the GCD of $x^6+x^3+1$ and $x^8+x^4+1$ is also a (positive) divisor of $3$. Therefore the GCD will be one or three.

Let $x\in\mathbb{N}$ be given. Let us consider all cases for $x$ modulo three. If $x\equiv +1 \pmod 3$, both $x^6+x^3+1$ and $x^8+x^4+1$ are clearly zero modulo three, which means that $\gcd(x^6+x^3+1, x^8+x^4+1)$ is really $3$ in that case. If $x\equiv 0 \pmod 3$ or $x\equiv -1 \pmod 3$, then $x^6+x^3+1 \equiv 0+1 \not\equiv 0 \pmod 3$, so three does not divide $x^6+x^3+1$, so the GCD has to be one in those cases, which was what you wanted to prove.

Nowhere did we use the property that $x$ is a prime number.