Artificio de reducción --por combinaciones lineales

Primos relativos significa que no tienen divisor común (su MCD es 1). Entonces "no son primos relativos" se traduce a "tienen un divisor común $d$ distinto de 1". Sea pues $d$ un divisor común de $n^2+1$ y $(n+1)^2+1$. Entonces $d$ divide a su diferencia $2n+1.$  Pero también divide a su suma $(2n+1)^2+5.$ Entonces $d$ es divisor común de $2n+1$ y $(2n+1)^2+5$. Pero si divide a $2n+1$ también divide a su cuadrado. De aquí que $d$ divide a 5. Es decir, $d=5.$

Con esta información, se concluye que $2n+1$ es múltiplo de 5, es decir, $2n=-1$(mod 5). En otras palabras, $2n=4$(mod 5). De aquí que $n$ es de la forma $5k+2$ para $k=0,1,2,\ldots.$ (El lector lo puede comprobar directamente haciendo la tabla de las clases residuales  (módulo 5) de$n, n^2 y (n+1)^2.$)

Nota:

El método de reducción (en la primera parte) es más claro si uno lo ve como la búsqueda de los multiplicadores adecuados $x,y$ --en la aplicación de la propiedad "si $d$ es divisor común de $a,b$ entonces es divisor de $ax+by$ ":

$n^2+1$ lo multiplico por -1

$n^2+2n+2$ lo multiplico por 1

Suma $=2n+1$

De nuevo:

$n^2+1$ lo multiplico por -4: $-4n^2-4$

$2n+1$ lo multiplico por $2n$: $4n^2+2n$

Suma $=2n-4=2n+1-5$

Y el resultado se hace obvio.