Find all possible values of $\gcd(n^2+3, (n+1)^2+3)$. Let $n \in \mathbb{N}$. Find all possible values of $\gcd(n^2+3, (n+1)^2+3)$. 
I began this problem giving some values for $n$ and I found that $\gcd(n^2+3, (n+1)^2+3)=1$ for most of $n$ I tried, but  if $n=6$, then $\gcd=13$.
Then I tried to prove that only for $n=6$, $\gcd \neq 1$ but I couldn't. 
Can someone help me with this problem?  
 A: I think that I just solve it:
Let $d=gcd(n^2+3, (n+1)^2+3).$ By the property $\gcd(a,b)=\gcd(a,b-a)$, we obtain:
$$d=\gcd(n^2+3,2n+1).$$
Since $d \mid n^2+3,$ we have $n^2+3=ds$ for some integer $s$. 
Similarly, $2n+1=dr$ for some integer $r$, and by this relation we obtain: $4n^2=d^2 r^2 -2dr +1 \iff 4ds=4(n^2+3)=d^2 r^2 -2dr +13$.
Hence, it must be clear that $13=dq$ for some integer $q$. Then $d \mid 13$.
So $d=13$ or $d=1$ since $13$ is prime. 
It is correct?
A: We assume the Lemma that if $\gcd(a,b)=1$ and $c$ is an integer, then $\gcd(a,bc)=\gcd(a,c).$
Also, that in general: $\gcd(a,b)=\gcd(a,b-ak)$ for any integer $k.$
Then $$\begin{align}
\gcd(n^2+3,(n+1)^2+3)&=\gcd(n^2+3,(n+1)^2+3-(n^2+3))\\
&=\gcd(n^2+3,2n+1)\\
&=\gcd(n^2+3-3(2n+1),2n+1)\\
&=\gcd(n(n-6),2n+1)\\
&=\gcd(n-6,2n+1)\quad \quad\text{ since }\gcd(n,2n+1)=\gcd(n,2n+1-2n)=1\\
&=\gcd(n-6,2n+1-2(n-6))\\
&=\gcd(n-6,13)
\end{align}$$
So the GCD is $13$ when $n-6$ is divisible by $13$ and $1$ otherwise.
A: Lemma $\ \ (f(n\!+\!1),f(n))\, =\, (n-2a,4a+1)\,\ $ for $\ f(n) = n^2+a\ \ $ [OP is $\,a = 3]$
$\begin{align}{\bf Proof}\ \ \ \  (f(n\!+\!1),f(n)) &\,=\, (2n+1,\,f(n))\ \ \ \ \ \ \:\! {\rm by\ \ } 2n\!+\!1 = f(n\!+\!1)-f(n)\ \ \rm and\ Euclid\\[.2em]
&\,=\, (\color{#c00}2n+1,\,4a+1) \ \ \ {\rm by}\ \ f(\color{#0a0}n) \equiv 4f(\color{#0a0}{\tfrac{\!-\!1}2})\equiv 4a\!+\!1\!\!\!\pmod{\color{#0a0}{n\equiv \tfrac{\!\!-1}2}}\\[.2em]
&\,=\, (n-2a,\, 4a+1)\ \ \ {\rm via\ scale\  by}\ \ \color{#c00}{2^{-1}}\equiv -2a\!\!\!\!\underbrace{({\rm mod}\,\ {4a\!+\!1})}_{\textstyle 1\equiv -4a\equiv \color{#c00}2(-2a)}
\end{align}$
where the $\rm\color{#0a0}{fractional}$ evaluation follows by this Theorem.
Remark $ $ See here for a more general way to do what we did above by evaluation at fractions - by instead scaling by leading coef's coprime to the gcd (which preserves the gcd), e.g. above by $(2,2n\!+\!1)=1$ we can scale $\,n^2+a\,$ by $\,2\,$ to get $\,(\color{#c00}{2n})n+2a\equiv (\color{#c00}{-1})n+2a\pmod{\!\color{#c00}{2n+1}}\,$ so $\,(2n+1,n^2+a) = (2\color{#0a0}n+1,\color{#0a0}{n-2a})= (2(\color{#0a0}{2a})+1,n-2a)\,$ by $\,\color{#0a0}{n\equiv 2a\pmod{n-2a}}\,$ using gcd mod reduction (congruence form of reduction step of Euclidean algorithm)
A: $$\gcd(n^2+3,(n+1)^2+3)=\gcd(n^2+3,2n+1)=\gcd(4n^2+12,2n+1)=$$
$$=\gcd(4n^2+4n+1-4n+11,2n+1)=\gcd(4n-11,2n+1)=$$
$$\gcd(4n+2-13,2n+1)=\gcd(13,2n+1).$$
Can you end it now?
A: The Euclidean algorithm in $\mathbb Q[n]$ gives
$$
13 =(2 n + 3)(n^2 + 3)+(1 - 2 n)((n + 1)^2 + 3)
$$
Therefore, the gcd is either $1$ or $13$.
Both values occur: $1$ occurs for $n=0$ and $13$ occurs for $n=6$.
In fact, $13$ occurs exactly when $n \equiv 6 \bmod 13$.
