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. 
 A: Let $d=\gcd(n^3-1, n+1)$. Then $d \mid (n^3-1)$ and $d \mid (n+1)$. So $d$ will divide any linear combination of $n^3-1$ and $n+1$. In particular, $d \mid n^2(n+1)-(n^3-1)$. Thus $d \mid n^2+1$. Further more we can say $d \mid n(n+1) - (n^2+1)$. Thus $d \mid n-1$. Now that $d$ is a common divisor of both $n+1$ and $n-1$. This implies $d \mid (n+1)-(n-1)=2$. Thus $d=1 \text{ or } 2$. But $n$ being even implies $n+1$ must be odd. Thus $d=1$. 
A: Hint:  You need $\gcd (a,b) = \gcd (a, b-a)$, so $\gcd (n^3-1, n^2(n+1))=\gcd (n^3-1,n^3+n^2)=\gcd (n^3-1,n^2+1)$  Keep going in this vein.
A: 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.$$
A: Hint: $n^3+1$ is definitely a multiple of $n+1$, since $a^3+b^3=(a+b)(a^2-ab+b^2)$.
