My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
restin84 is offline  
 
December 14th, 2011, 03:30 PM   #2
Senior Member
 
MarkFL's Avatar
 
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:



Thus, .
MarkFL is offline  
December 14th, 2011, 03:47 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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?!?".
CRGreathouse is offline  
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
proglote is offline  
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?
restin84 is offline  
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:
gives .
proglote is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.