$\forall n\in\mathbb{Z}$, find the $\gcd(n^2+1, (n+1)^2+1)$?

Question

$\forall n\in\mathbb{Z}$, find the $\gcd(n^2+1, (n+1)^2+1)$.

I think this is a simple exercise, but I get this:

$(n+1)^2+1=n^2+2n+2$.

$n^2+2n+2 = (n^2+1)+(2n+1)$

then $\gcd(n^2+1, (n+1)^2+1)=\gcd(n^2+1, 2n+1)$

and $\displaystyle n^2+1 = \frac{n(2n+1)}{2}+\left(-\frac{n}{2}+1\right)$

then $\gcd(n^2+1, 2n+1)=\gcd(2n+1, \frac{n}{2}-1)$.

But gcd is on integer numbers and $\dfrac{n}{2}-1$ is not always an integer number, so, I need some help?

Answer 1

Let $d=\gcd(n^2+1, (n+1)^2+1)$

So $d$ divides their difference

$d|2n+1$ so by multiplication with $n$ one gets $d|2n^2+n$

But $d|2n^2+2$ so $d|n-2$ so $d|2n-4$ so $d|5$

By considering all the residues modulo $5$ of $n^2+1$ and $(n+1)^2+1$ we can see that $\gcd$ is $5$ if $n\equiv2$ mod $5$, and $1$ otherwise.

Answer 2

Note that $$(2n+3)(n^2+1) - (2n-1)((n+1)^2+1) = 5.$$

To get this equation, set $(n+a)(n^2+1)-(n+b)(n^2+2n+2) = c$ for some constants $a,b,c$, and equate coefficients. This gives $b = -\tfrac{1}{2}$, $a = \tfrac{3}{2}$, and $c = \tfrac{5}{2}$. Then, multiply both sides by $2$.

Hence, $\text{gcd}(n^2+1,(n+1)^2+1)$ divides $5$ (which is prime).

Then, since $n^2+1 \equiv 0 \pmod{5}$ iff $n \equiv 2,3 \pmod{5}$ and $(n+1)^2+1 \equiv 0 \pmod{5}$ iff $n \equiv 1,2 \pmod{5}$ we have that $$\text{gcd}(n^2+1,(n+1)^2+1) = \begin{cases}5 & \text{if} \ n \equiv 2 \pmod{5} \\ 1 & \text{otherwise}\end{cases}.$$

Answer 3

Your step that says $\displaystyle n^2+1 = \frac{n(2n+1)}{2}+\left(-\frac{n}{2}+1\right)$ is correct but not useful. We are working in the naturals and this threatens (if $n$ is not even) to takes us out of the naturals.

If we just make a spreadsheet and try the small numbers we find that the GCD is $1$ unless $n\equiv 2 \pmod 5$, in which case it is $5$. We can see that if $n \equiv 2 \pmod 5$, $n^2+1 \equiv (n+1)^2+1 \equiv 0 \pmod 5$. Now we need to ask if there are any other numbers $k$ where $n^2\equiv (n+1)^2 \equiv -1 \pmod k$. This requires that $2n+1 \equiv 0 \pmod k$. We can factor $k$ demand that $2n+1 \equiv 0 \pmod p$ for some prime $p$ dividing $k$. If we square that we get $4n^2+4n+1\equiv 4n-3\equiv 0, n \equiv \frac 34 \pmod p$ where we take advantage of the fact that $\Bbb Z_p$ is a field to divide. Now $n^2 \equiv -1 \pmod p$ says $9 \equiv -16 \pmod p$ and the only prime is $5$. So the $\gcd$ is $1$ unless $n \equiv 2 \pmod 5$ in which case it is $5$.