<s>[INST] $2n+1$ and $n^2+1$ are always coprime or their gcd is $5$ Using a spreadsheet, it can be inferred that when $n≡2[5]$, then $\gcd(n^2+1,2n+1)=5$, else $\gcd(n^2+1,2n+1)=1$.
Indeed, when $n≡2[5]$, $n^2+1$ and $2n+1$ can easily be shown to be multiples of $5$, so their gcd is at least $5$. But then, I can't see how to complete the proof.
 [/INST] Let $d=\gcd(2n+1,n^2+1)$. Then since $d\mid 2n+1$ and $d\mid n^2+1$, we must also have $$d\mid(n^2+1)-(2n+1)=n(n-2)\;.$$ Clearly $\gcd(n,2n+1)=1$, and $d\mid 2n+1$, so $\gcd(n,d)=1$, and therefore $d\mid n-2$. By definition $d\mid 2n+1$, so $d\mid(2n+1)-2(n-2)=5$, and therefore $d=1$ or $d=5$.
The problem doesn’t require you to do so, but you can easily check that $d=5$ if and only if $n\equiv2\pmod 5$, so that $5\mid n-2$. 
</s>