<s>[INST] Are $1+p^3+p^6$ and $1+p^4+p^8$ coprime? 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.
 [/INST] 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$.
</s>