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

Clearly when $n=0$ the polynomials are relatively prime (gcd = 1).

notice that $2n+1$ is always odd, while $n^2 + 1$ is always even. Thus the gcd can never contain $2$ as a factor.

Let $d | n^2 + 1$ and $d | 2n + 1$, then [because $a|b$ implies $a|kb$] we have


*

*$d|2n^2 + 2$

*$d|2n^2 + n$


and [because $a|b$ and $a|c$ imply $a|c-b$] this gives us


*

*$d|n-2$


we can use this (since it's degree 1) to cancel out the $n$ in our assumption $d | 2n + 1$ to get


*

*$d|n + 3$


and again to get


*

*$d|5$


Since $5$ is prime, we've found that the GCD of the polynomials for some $n$ must be either $1$ or $5$.

We would now like to find out exactly when the GCD is 5 (i.e. when $5|2n+1$ and $5|n^2+1$ and when it's one. For this we can use the equivalence [$a|b$ iff $b \equiv 0 \pmod a$]. So we only need to check 5 values.
n | 2n+1 | n^2+1
----------------
0 | 1    | 1
1 | 3    | 2
2 | 0    | 0     !
3 | 2    | 0
4 | 4    | 2

therefore we have proved the result:
$$\gcd(2n+1,n^2+1) = \begin{cases}5 & \text{when } n \equiv 2 \mod 5 \\ 1 & \text{otherwise}\end{cases}$$
