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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2012 at 9:48
  • $\begingroup$ @ChirayuShishodiya: Could you elaborate this a bit? $\endgroup$
    – draks ...
    Nov 24, 2012 at 12:34

1 Answer 1

6
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ To rewrite your argument, $$(1-2n) A_{n+1} + (3+2n)A_n = 13$$+1 $\endgroup$
    – user17762
    Nov 24, 2012 at 10:01
  • $\begingroup$ @Marvis Yes, once you know it, one can write it down in this nice compressed form. But I think it would be hard to find that relation from scratch. $\endgroup$ Nov 24, 2012 at 14:40
  • $\begingroup$ 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)$ $\endgroup$
    – Yonatan
    Nov 24, 2012 at 16:01
  • $\begingroup$ @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$. $\endgroup$
    – user17762
    Nov 24, 2012 at 21:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .