elementary number theory - Showing $gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

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

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.