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?
 A: Let $d=\gcd(n^2-1,3n+1)$. 


*

*$n$ odd: $n^2-1$ and $3n+1$ are both even, so $d$ is at least $2$.

*$n$ even: As $n^2-1$ and $3n+1$ are both odd, $d$ must be odd. Also: $d\mid 9n^2-1=(3n+1)(3n-1)$ and $d\mid n^2-1$ so $d\mid 8n^2$, and then (being odd): $d\mid n^2$. Because also $d\mid n^2-1$ we find $d\mid 1$, i.e. $d=1$. 

A: $\gcd(n^2-1, 3n+1)=\gcd(3n^2-3, 3n+1)=\gcd(n+3, 3n+1)=\gcd(n+3, 8)$.
if $n$ - odd then $\gcd(n+3, 8)>=2$,
if $n$ - even then $n+3$ - odd and $\gcd(n+3, 8)=1$.
A: 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$.
A: If $d$ divides both  $n^2-1,3n+1$
$d$ must divide $n(3n+1)-3(n^2-1)=n+3$
$d$ must divide $3(n+3)-(3n+1)=8$
$d$ must divide $(n+3,8)= \begin{cases}8&\mbox{if} n+3=8m\iff n\equiv5\pmod8 \\ 
4& \mbox{if }n+3=4(2t+1)\iff n\equiv1\pmod8\\2& \mbox{if } n+3=2(2r+1)\iff n\equiv3\pmod4\\1& \mbox{if } n+3=2s+1\iff n\equiv0\pmod2\end{cases}$
where $m,t,r,s$ are arbitrary integers
