My Math Forum GCD and Fibonacci

 Number Theory Number Theory Math Forum

 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_n-1 ). I know that the result will be gcd( f_n, f_n-1) = 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_n-1) this looks something like... f_n = 1 * f_n-1 + f_n-2 f_n-1 = 1 * f_n-2 + f_n-3 f_n-2 = 1 * f_n-3 + f_n-4 . . . 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: 521 Math Focus: Calculus/ODEs Re: GCD and Fibonacci I would use the algorithm to state: $\gcd$$F_n,F_{n-1}$$=\gcd$$F_n-F_{n-1},F_{n-1}$$=\gcd$$F_{n-2},F_{n-1}$$=\gcd$$F_{n-1},F_{n-2}$$$ Thus, $\gcd$$F_n,F_{n-1}$$=\gcd$$F_2,F_1$$=\gcd$$1,1$$=1$.
 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 $\gcd(F_n,F_n-1)$ rather than $\gcd(F_n,F_{n-1})$ 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 : $\gcd(F_{m}, F_{n})= F_{\gcd(m,n)}$. The above is obtained taking $m= n-1.$
 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 $\LaTeX$ For example, Code: $x= \frac{-b \pm \sqrt{b^{2} - 4ac}}{2a}$ gives $x= \frac{-b \pm \sqrt{b^{2} - 4ac}}{2a}$.

 Tags fibonacci, gcd

,

,

,

# Fibonacci gcd's

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top