Show that if $n$ is an odd integer then $\gcd (n + 1, n^2 + 1) = 2$.
Given $n$ is an odd integer, we write it as $2k+1$ for some integer $k$. That means $n^2 = (2k+1)^2 = 4k^2 +4k + 1$.
Then
$$\begin{align} \gcd (n+1, n^2 +1) &= \gcd (\; 2k+2\; , \; 4k^2 +4k + 2 \; ) \\ \\ &= \gcd (\; 2(k+1) \; , \; 2(2(k^2+k)+1) \;) \\ \\ &= 2 \times \gcd (\; k+1 \; , \; 2k(k +1) + 1 \;) \end{align}$$
Our aim is to show that $\gcd (\; k+1 \; , \; 2k(k +1) + 1 \;) = 1$.
Let's say this gcd is $g$, so by the Linear Combination Theorem, for any integers $x$ and $y$,
$$ g \mid (k+1)x + (2k(k +1) + 1)y $$
If we choose $x=-2k$ and $y=1$, we have
$$ g \mid (k+1)(-2k) + (2k(k +1) + 1) $$
which reduces to
$$ g \mid 1 $$
Which means the gcd $g$ must be 1, since it divides 1. So we have shown that $\gcd (\; k+1 \; , \; 2k(k +1) + 1 \;) = 1$. This leaves us with the desired result, for odd $n$
$$ \gcd (n+1, n^2 + 1) = 2 $$