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.

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