perplexus.info :: Sequences : Fibo's common divider

Fibo's common divider (Posted on 2020-06-10)

1,1,2,3,5,8,13...

Given basic Fibonacci sequence (as above) with a₁=1 and a₂=1 evaluate the GCD of a₇₇₀ and a₁₀₀₀.

No Solution Yet Submitted by Ady TZIDON

Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

soln (spoiler)

| Comment 1 of 4

Here, we express the GCD of a and b as (a,b), and the i'th F number as F(i).

We use the remarkable theorem: (F(a),F(b)) = F(a,b)

Here, a = 770 = 2 * 5 * 7 * 11 and b = 1000 = 2^3 * 5^3

so... (a,b) = 10 and thus, F(10) = 55, is our answer.

Please note: I had help.

Edited on June 10, 2020, 2:46 pm

Posted by Steven Lord on 2020-06-10 14:36:57

Please log in:

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

Chatterbox:


perplexus dot info