# Prove that for $A_k$ and $A_{k+1}$ when $A_n=n^2+3$, their largest common prime factor $\leq 13$

I need to prove that for any two following numbers $A_i$ and $A_{i+1}$ from the sequence $A_n=n^2+3$, their largest common prime factor must be $\le13$.

It feels like I need to use the fundamental theorem of arithmetic, but I couldn't figure how. Any ideas?

-
I would try to be prove this by contradiction i.e. assume that the two numbers have a largest common prime factor greater than 13. In the end, we may arrive at a statement which contradicts our assumption. –  Chirayu Shishodiya Nov 24 '12 at 9:48
@ChirayuShishodiya: Could you elaborate this a bit? –  draks ... Nov 24 '12 at 12:34

Try Euclid's algorithm to determine $d=\gcd(A_n,A_{n+1})$ as far as it carries us with symbolic expressions: As $A_n=n^2+3$ and $A_{n+1}=(n+1)^2+3$, we have $A_{n+1}-A_n=2n+1$, hence $d|2n+1$. But $d$ must also divide $2A_n-n(2n+1)=6-n$ and hence also $(2n+1)+2(6-n)=13$. So we find an even stronger claim:
The greatest common (not necessarily prime) divisor of $A_n$ and $A_{n+1}$ is either $1$ or $13$.
To rewrite your argument, $$(1-2n) A_{n+1} + (3+2n)A_n = 13$$+1 –  user17762 Nov 24 '12 at 10:01
Just to explain Hagen's proof: if $d|x$ and $d|y$, than $d|ax+by$ (that's how Euclid's algorithm works). Therefore, if $d|2n+1$ and $d|A_n$, then $d|2A_n-n(2n+1)$. And if $d|6-n$ and $d|2n+1$, $d|(2n+1)-2(6-n)$ –  Yonatan Nov 24 '12 at 16:01
@HagenvonEitzen Yes true. Also, to show that we cannot eliminate $13$, we have that $13 \vert 39 = A_6$ and $13 \vert 52 = A_7$. And in general, $\gcd(A_{13k+6}, A_{13k+7}) = 13$. For the rest of the $n$'s the $\gcd$ is $1$. –  user17762 Nov 24 '12 at 21:23