Prove that gcd$(n^2+1, (n+1)^2+1)$ is either 1 or 5

Question

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

Answer 1

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

Answer 2

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

Answer 3

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