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

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$.

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.