<s>[INST] 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?
 [/INST] 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, 
</s>