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

• If my Euclidean algorithm type calculations are correct, there are polynomials $a, b \in \mathbb{Z}[x]$ such that $a(x) (x^6 + x^3 + 1) + b(x) (x^8 + x^4 + 1) = 3$. So, that would imply that $\gcd(p^8+p^4+1, p^6+p^3+1)$ is either 1 or 3 for any integer $p$ (regardless of whether or not $p$ is prime). – Daniel Schepler Jul 9 '18 at 23:37
• @DanielSchepler Explicitly, $$(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.$$ – Jeppe Stig Nielsen Jul 9 '18 at 23:46
• @DanielSchepler I have a canned C++ program that does this by explicit extended Euclidean ( and creates formatted Latex), same outcome as Jeppe. Very clever, I would never have checked for that. – Will Jagy Jul 9 '18 at 23:52
• My comment came from feeding gcdext(x^6+x^3+1,x^8+x^4+1) into PARI/GP (extended GCD with Bézout's identity). It gives a vector of polynomials with fractions in the coefficients of the polynomials, but upon scaling with a factor three (PARI/GP 3*%) I got output almost in TeX format (it did take me one comment edit to get it right). I still think @DanielSchepler should write a full answer. It is clear enough that $x$ modulo $3$ (you run through cases $0,+1,-1$) determines whether the GCD is 1 or 3. No application of $x$ being prime or not. – Jeppe Stig Nielsen Jul 10 '18 at 0:19

## 3 Answers

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.

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

• So, on each of lines 3 through 7 of the display, the remainder is in the ideal $\langle x^8+x^4+1, x^6+x^3+1 \rangle$ of $\mathbb{Z}[x]$. i.e. from line 7 you will get $-3 \in \langle x^8+x^4+1, x^6+x^3+1 \rangle$. – Daniel Schepler Jul 9 '18 at 23:51
• @DanielSchepler sure. The point of writing the program was that it typesets the whole thing. Also does it as a simple continued fraction, which is a method I like. Anyway, excellent call on checking the gcd as polynomials. – Will Jagy Jul 9 '18 at 23:55