Find the Greatest common divisor of the 2012th and 2013th term of the Fibonacci series.

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