Consecutive Fibonacci Numbers Relatively PrimeDate: 11/17/2001 at 13:32:56 From: Beverly Miner Subject: Discrete math I'm trying to show that two consecutive Fibonacci numbers are relatively prime. I'm trying proof by induction. I've been working with mods but am making little progress. Date: 11/20/2001 at 13:33:19 From: Doctor Paul Subject: Re: Discrete math F_n denotes the nth Fibonacci number. Proof (1): Using the Euclidean algorithm for finding the gcd(F_(n+2), F_(n+1)), we have: F_(n+2)=1*F_(n+1) + F_n F_(n+1)=1*F_n + F_(n-1) . . . F_4=1*F_3 + F_2 F_3=2*F_2 + 0 Substituting numbers in the last two lines gives: 3 = 1*2 + 1 2 = 2*1 + 0 This means that gcd(F_(n+2),F_(n+1)) = F_2 = 1, and thus any two consecutive Fibonacci numbers are relatively prime. Proof (2) - by contradiction Let F_n and F_(n+1) be any two consecutive Fibonacci numbers and suppose there is an integer d > 1 such that d divides F_n and d divides F_(n+1). Then F_(n+1) - F_n = F_(n-1) will also be divisible by d (if d divides a and d divides b, then a = d*m and b = d*n for some integers m and n. Then a - b = d*m - d*n = d * (m-n), so d divides (a - b) as well). But now notice that F_n - F_(n-1) = F_(n-2) will also be divisible by d. We can continue this way showing that F_(n-3), F_(n-4), ... , and finally F_1 = 1 are all divisible by d. Certainly F_1 is not divisible by d > 1. Thus we have a contradiction that invalidates the assumption. Thus it must be the case that F_n and F_(n+1) are relatively prime. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/