<s>[INST] 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?  
 [/INST] 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.
</s>