<s>[INST] Prove that $\gcd (n^3-1,n+1)=1$ for all even $n$. Prove that if $n$ is even, then 
$$\gcd(n^3-1,n+1)=1.$$
I really don't have a clue with this one. Any help would be appreciated. 
 [/INST] If you polynomial long divide $n+1$ into $n^3-1$ (or use the Euclidean Algorithm), you obtain the expression:
\begin{align*}
n^3-1&=(n+1)(n^2-n+1)-2 \\
\implies 2&=(n+1)(n^2-n+1)-(n^3-1)
\end{align*}
The greatest common divisor of $n^3-1$ and $n+1$ divides both terms on the right, so it must divide their difference, 2, as well. So it must be either 1 or 2.
Note that $n+1$ is odd though, so the $\gcd$ cannot be 2. Therefore $$\gcd(n^3-1,n+1)=1.$$
</s>