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?
 A: 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$. 
A: 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, 
A: 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.
A: 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.
A: Let $d=\gcd(n^3+1,n^2+2)$ then we have:
 $d|n^3+2n\Rightarrow\ d|2n-1\Rightarrow\ d|2n^2-n\Rightarrow\ d|2n^2+4\Rightarrow\ d|n+4\Rightarrow\ d|2n+8\Rightarrow\ d|9\Rightarrow\ d=1,3,9$
A: The extended Euclidean algorithm gives
$$
9 = (2 n + 1)(n^3+1)+(-2 n^2 - n + 4)(n^2+2)
$$
and so $\gcd(n^3 + 1, n^2 + 2)$ divides $9$.
