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?

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