All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
GCD of Fibonacci (Posted on 2012-12-06) Difficulty: 2 of 5
Find the Greatest common divisor of the 2012th and 2013th term of the Fibonacci series.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 2 of 2 |

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Let's start at 2,3. Their GCD is 1. No integer larger than 1 will divide them both.

The next number, 5, is the result of 2+3. For a number to divide both 3 and 5 it would have to divide 5-3 = 2, but then it would be dividing both 2 and 3, which we said it didn't.

Generalize:

GCD(F(2),F(3)) = 1

Induction:

Given GCD(F(n),F(n+1)) = 1, i.e., no larger number divides them both.

F(n+2) = F(n+1) + F(n)

For an integer to divide both F(n+2) and F(n+1) it would also have to divide F(n), so if F(n) and F(n+1) have no common divisors, neither do F(n+1) and F(n+2).

Therefore no two successive Fibonacci numbers have any common divisor and that includes the 2012th and the 2013th.

GCD(F(2012),F(2013)) = 1.

BTW, those two numbers are:

 2201074898489654851295345882693918685635408879838265301853440274470213648026375
40732468029466411189363203490494290194618192968681937916254417517239483953980237
00736885668265215519156244034360475492630269599512101705391232258518057095494524
80163241274159911091452903300192054343185198788563257726939950967985095124747544
92603619952052903566165986170638039674771671804843811737659286789406659220055622
6235866548588549337858

and

 3561413997540486142674781564382874188700994538849211456995042891654110985470076
81842108023696124387571153754338867627733987596382446633443240373075037690602674
18198890364644017882322130025229348972999288441928035071576477645424663276131346
05502785287441134627457615461304177503249289874066244145666889138852687147544158
44315520415795029412917778511946444666837416374670096937243852618290676814374089
1051274219441912520127

found by

10   N=2:F1=1:F2=2
20    for I=3 to 2013
30       F3=F1+F2
40       F1=F2:F2=F3
50    next
60   print F1:print F2


  Posted by Charlie on 2012-12-06 13:28:15
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information