3
$\begingroup$

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?

  • 0
    @Ch$i$rayuShishodiya: Could you elaborate this a bit?2012-11-24

1 Answers 1

6

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$.

  • 0
    @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$.2012-11-24