Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 6 down vote accepted

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

share|improve this answer
2  
To rewrite your argument, $$(1-2n) A_{n+1} + (3+2n)A_n = 13$$+1 –  user17762 Nov 24 '12 at 10:01
    
@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. –  Hagen von Eitzen Nov 24 '12 at 14:40
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.