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,,

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