<s>[INST] 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?
 [/INST] 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
</s>