All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
GCD of Fibonacci 2 (Posted on 2016-03-23) Difficulty: 2 of 5
This is an extension of GCD of Fibonacci.

Denote the nth term of the Fibonacci sequence as F(n), with F(0)=0 and F(1)=1. Let S_n be the set {F(n), F(n+1), F(n+2), F(n+3)}.

For what values n does there exist a pair of numbers from S_n with a GCD greater than 1?

See The Solution Submitted by Brian Smith    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
possible solution | Comment 1 of 2
Wikipedia says that two consecutives terms of a Fibonacci series are coprimes. 

So: 

F(n) and F(n+1) are coprimes.

But the sum of two coprimes numbers is coprime with both. Then F(n+2), F(n+1), F(n) are relatively primes

Then F(n+3)=F(n+2)+Fn(n+1)=F(n)+2F(n+1).     F(n) and F(n+1) are coprimes but if F(n) is even then F(n+3) will be even. 

So, if F(n) is even F(n+3) is even and GDC is 2. 
This is confirmed by a look to the Fibonacci sequence which is odd,odd,even,odd,odd,even...

Edited on March 23, 2016, 10:05 am
  Posted by armando on 2016-03-23 09:53:30

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information