If $n \in \mathbb{N}\setminus\{1\}$ then $\gcd(n^2-1,3n+1)=1$ if and only if $n$ is even If $n\in\mathbb N\setminus\{1\}$ then $\gcd(n^2-1,3n+1)=1$ if and only if $n$ is even.
Can somebody help me prove this problem?

Let $a=n^2-1$, and let $b = 3n+1$.

Let $d = \text{gcd}(a,b)$.

First, suppose $n$ is odd. 

Then $a,b$ are both even, so $d > 1$.

Next, suppose $n$ is even.

Then $a,b$ are both odd, so $d$ must be odd.

Now simply note that
\begin{align*}
9a-(3n-1)b &= 9(n^2-1)-(3n-1)(3n+1)\\[4pt]
&=(9n^2-9)-(9n^2-1)\\[4pt]
&=-8\\[4pt]
\end{align*}
hence $d$ must divide $8$. 

Since $d$ is odd, it follows that $d=1$.
