Prove that gcd$(n^2+1, (n+1)^2+1)$ is either 1 or 5 My try to solve this question goes as follows:
$g=gcd(n^2+1, (n+1^2)+1) = gcd(n^2+1, 2n+1) = gcd(n^2-2n, 2n+1)$.
By long division: 
$$n^2-2n = -2n(2n+1) + 5n^2$$
Since $g$ divides $n^2-2n$ and $g$ divides $(2n+1)$, $g$ divides $5n^2$. However, I need to show that $g$ is prime in order to show that it divides $5$ or $n^2$. I am stuck at this point.
Any Ideas,,
 A: Clearly $$\gcd(n^ 2+1,(n+1)^2+1)\mid \bigl((n+1)^2+1\bigr)-\bigl(n^ 2+1\bigr)=2n+1,$$ 
hence also 
$$\gcd(n^ 2+1,(n+1)^2+1)\mid (2n+1)n-2(n^2+1)=n-2 $$
as well as
$$\gcd(n^ 2+1,(n+1)^2+1)\mid (2n+1)n-2(n^2+1)=2n+1-2(n-2)=5. $$
This leaves only the possibilites $1$ and $5$ (which are both  possible as can be seen by checking the cases $n=1$ and $n=2$)
A: Since $\gcd(n,2n+1)=\gcd(n,1)=1$, you can keep going:
$$\gcd(n^2-2n,2n+1)=\gcd(n(n-2),2n+1)=\gcd(n-2,2n+1)=\gcd(n-2,5)\in\{1,5\}$$
The key reduction here is the gcd property $\gcd(a,b)=1\implies\gcd(ac,b)=\gcd(c,b)$.
A: mod $\,  (f(n),\!\!\overbrace{n^2\!+\!1}^{\color{#c00}{\Large n^2\ \equiv\  -1}}\!\!\!)\!:\ \ 0\equiv \overbrace{\color{#c00}{n^2}\!+\!2n\!+\!2}^{\large f(n)}\equiv 2n\!+\!1\ \Rightarrow\  0\equiv \overbrace{(1\!+\!2n}^{\Large \color{#0a0}w})(\overbrace{1\!-\!2n}^{\Large\color{#0a0}{ \bar w}})\equiv 1\!-\!4\color{#c00}{n^2}\equiv 5$
Or in Gaussian integers $\, \Bbb Z[i] \cong \Bbb Z[n]/(n^2\!+\!1)\!:\,$ $ w\! =\! f(i)\! =\! 1\!+\!2i\,\Rightarrow\, \bmod w\!:\ 0 \equiv \color{#0a0}{w\,\bar w} = 5$
Corollary $\ \gcd(f(n),n^2\!+\!1)\mid f(i)\overline{f(i)}\ $ for any polynomial $f\in\Bbb Z[x]$
