Find $d \in \mathbb{Z}^+$ s.t. $d \vert n^2 + 1$ (Ill call this $a$) and $d \vert (n+1)^2 +1$ (this $b$)
so I know $\exists x,y \in \mathbb{Z}$ s.t.
($n^2 + 1)x + (n^2 + 2n + 2)y = d$
(I computed some values to see what is goin on, the pattern, then got the idea to use division algorithm after)
Now for positive integer values of 1,2,3,4,5 for $a$ and $b$ we get
2,5 ; 5,10 ; 10,17 ; 17,26 ; 26,37
So they build on each other and the gap increases by 3,5,7,..
should I write $b$ in terms of $a$? so
$n^2 + 2n + 2 = (n^2 + 1)(1)$ + ($2n + 1$) ; my $r$ is $2n + 1$
where do I go from here?
Id prefer a hint or lemma to use instead of a full solution.
To continue the Euclidean algorithm, it is either necessary to allow rational coefficients or to allow multiples. I will show the second type. $$ n^2 +2n+ 2 = (1)(n^2 + 1) + (2n+1) $$ $$ 4(n^2 + 1) = (2n-1)(2n+1) + 5 $$
Now the back substitution; you can express 5 as a combination of $n^2 + 2n+2$ and $n^2 + 1,$ it is just that the coefficients are also polynomials. You should do that part, $$ 5 = f(n) (n^2 + 2n+2) + g(n) (n^2 + 1) $$ This means that the common divisor $d$ is either $1$ or $5,$ as it must divide $5$