December 14th, 2011, 03:01 PM  #1 
Member Joined: Sep 2009 Posts: 71 Thanks: 0  GCD and Fibonacci
I have a problem for a cryptography course. It asks me to use the generalized Euclid Algorithm to determine gcd( f_n, f_n1 ). I know that the result will be gcd( f_n, f_n1) = 1 but I am having a hard time showing this. What I have written... take gcd of fibonacci numbers 8 and 5 gcd(8,5) by Euclid's Algorithm... 8 = 1 * 5 + 3 5 = 1 * 3 + 2 3 = 1 * 2 + 1 2 = 1 * 1 + 1 1 = 1 * 1 ===> gcd(8,5) = 1 in general for gcd(f_n, f_n1) this looks something like... f_n = 1 * f_n1 + f_n2 f_n1 = 1 * f_n2 + f_n3 f_n2 = 1 * f_n3 + f_n4 . . . f_1 = 1 I don't feel as if this is sufficient but I am not sure what else to do. 
December 14th, 2011, 03:30 PM  #2 
Senior Member Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 520 Math Focus: Calculus/ODEs  Re: GCD and Fibonacci
I would use the algorithm to state: Thus, . 
December 14th, 2011, 03:47 PM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: GCD and Fibonacci
Heh... I'm glad you answered that, Mark. When I read the problem I thought it was asking for rather than and was like "...just take one step of the algorithm and you're done?!?". 
December 14th, 2011, 04:12 PM  #4 
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Re: GCD and Fibonacci
The more general relation holds : . The above is obtained taking 
December 14th, 2011, 04:32 PM  #5 
Member Joined: Sep 2009 Posts: 71 Thanks: 0  Re: GCD and Fibonacci
Thanks a lot guys. How can I mark up my text so that I can get my posts more readable?

December 14th, 2011, 04:52 PM  #6 
Senior Member Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0  Re: GCD and Fibonacci
Use For example, Code: 

Tags 
fibonacci, gcd 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fibonacci matrix  gelatine1  Algebra  4  July 6th, 2013 08:47 PM 
A Fibonacci Puzzle  icemanfan  Math Events  1  May 11th, 2013 08:25 PM 
Fibonacci  tahir.iman  Number Theory  12  December 28th, 2012 04:53 AM 
Fibonacci  kobe745  Algebra  1  May 11th, 2011 10:58 AM 
Fibonacci mod Fibonacci  EPH  Number Theory  7  April 22nd, 2010 01:00 PM 