Prove that $\gcd (n^3-1,n+1)=1$ for all even $n$.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

Hint: $n^3+1$ is definitely a multiple of $n+1$, since $a^3+b^3=(a+b)(a^2-ab+b^2)$.