Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Question

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$.

I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = gcd(a+cb,b). So I can do things like decide that $\gcd(n^3 + 1, n^2 + 2) = \gcd((n^3+1) - n(n^2+2),n^2+2) = \gcd(1-2n,n^2+2)$ and then using Bezout's theorem I can get $\gcd(1-2n,n^2+2)= r(1-2n) + s(n^2 +2)$ and I can expand this to $r(1-2n) + s(n^2 +2) = r - 2rn + sn^2 + 2s$ However after some time of chasing this path using various substitutions and factorings I've gotten nowhere.

Can anybody provide a hint as to how I should be looking at this problem?

Answer 1

As you note, $\gcd(n^3+1,n^2+2) = \gcd(1-2n,n^2+2)$.

Now, continuing in that manner, $$\begin{align*} \gcd(1-2n, n^2+2) &= \gcd(2n-1,n^2+2)\\ &= \gcd(2n-1, n^2+2+2n-1)\\ &= \gcd(2n-1,n^2+2n+1)\\ &= \gcd(2n-1,(n+1)^2). \end{align*}$$

Consider now $\gcd(2n-1,n+1)$. We have: $$\begin{align*} \gcd(2n-1,n+1) &= \gcd(n-2,n+1) \\ &= \gcd(n-2,n+1-(n-2))\\ &=\gcd(n-2,3)\\ &= 1\text{ or }3. \end{align*}$$ Therefore, the gcd of $2n-1$ and $(n+1)^2$ is either $1$, $3$, or $9$. Hence the same is true of the original gcd.

Answer 2

Playing around along the lines you were exploring should work. Let's do it somewhat casually, aiming always to reduce the maximum power of $n$.

If $m$ divides both $n^3+1$ and $n^2+2$, then $m$ divides $n(n^2+2)-(n^3+1)$, so it divides $2n-1$. (You got there.)

But if $m$ divides $n^2+2$ and $2n-1$, then $m$ divides $2(n^2+2)-n(2n-1)$, so it divides $n+4$. (This move is slightly risky. In some cases this kind of move could introduce spurious common divisors. But (i) In this case it doesn't; and (ii) We will be checking at the end anyway whether our list of candidates is correct.)

But if $m$ divides $n+4$ and $2n-1$, then $m$ divides $2(n+4)-(2n-1)$, so it divides $9$.

We did not work explicitly with greatest common divisors, so we are not finished. We must show that $1$, $3$ and $9$ are all achievable. For $\gcd$ $1$, let $n=0$. For $\gcd$ $3$, let $n=2$. For $\gcd$ $9$, let $n=4$.

Answer 3

I'm carrying out a congruence procedure, so that you have different approaches.

If $p \, | \, n^3 + 1$ and $p \, | \, n^2 + 2$, then $2n \equiv 1 \pmod p$, which means $$ -8 \equiv 8n^3 = (2n)^3 \equiv 1^3 \equiv 1 \pmod p, $$ hence $9 \equiv 0 \pmod p$ and assuming $p$ is a prime means $p = 3$. This means the $\gcd$ is a power of $3$. Now I'm checking powers of $3$ by hand using congruences.

EDIT : As miracle's comment says, I got far too carried away by liking primes so much : a good way to say that this proof is done is that $9 \equiv 0 \mod p$ means $p \, | \, 9$, hence getting examples is enough to get our answer.

---

If $n \equiv 0 \pmod 3$, this $\gcd$ is clearly $1$.

If $n \equiv 1 \pmod 3$, $n^3 + 1 \equiv 1 \pmod 3$ so that the $\gcd$ is again $1$.

If $n \equiv 2 \pmod 3$, then $9 \, | \, n^3 + 1$ and $3 \, | \, n^2 + 2$. But letting $n = 3k+2$ we notice that \begin{align*} (3k+2)^3 + 1 & = (3k)^3 + 3 \cdot (3k)^2 \cdot 2 + 3 \cdot 3k \cdot 2^2 + 2^3 +1 \\& \equiv 9(k+1)\pmod{27} \end{align*} which is $0$ if and only if $k \equiv 2 \pmod 3$. Carry on! We get $$ (3k+2)^2 + 2 \equiv (3k)^2 + 2 \cdot (3k) \cdot 2 + 2^2 + 2 = 9k^2 + 12k + 6 \equiv 0 \pmod{27} $$ if and only if $$ 3k^2 + 4k + 2 \equiv 0 \pmod 9 $$ but reading this $\bmod 3$, we get $k \equiv 1 \pmod 3$, a contradiction.

I must say it is a little longer than the $\gcd$ proof : I expected people to put up to $\gcd$ proof, so I've shown this one instead. I like those proofs because they're mechanical ; I didn't have to think much to write it, I just chose to go this way and things always go as expected (assuming the question asks something that's true, obviously)... Now I've only proven that the $\gcd$ divides $9$ : again, to show that the $3$ possibilities actually happen, pull off examples like Andre Nicolas.

---

Hope that helps,

Answer 4

Let $\:\rm d = (n^3+1,\:n^2+2).\:$ Observe that $\rm \ d \in \{1,\:3,\:9\} \iff\ d\:|\:9\iff 9\equiv 0\pmod d\:.$

mod $\rm (n^3\!-a,n^2\!-b)\!:\ a^2 \equiv n^6 \equiv b^3\:$ so $\rm\:a=-1,\:b = -2\:\Rightarrow 1\equiv -8\:\Rightarrow\: 9\equiv 0\:. \ \ $ QED

Or, if you don't know congruence arithmetic, since $\rm\: x-y\:$ divides $\rm\: x^2-y^2$ and $\rm\: x^3-y^3$

$\rm n^3-a\ |\ n^6-a^2,\:\ n^2-b\ |\ n^6-b^3\ \Rightarrow\ (n^3-a,n^2-b)\ |\ n^6-b^3-(n^6-a^2) = a^2-b^3 $

Note how much simpler the proof is using congruences vs. divisibility relations on binomials. Similar congruential proofs arise when computing modulo ideals generated by binomials.