Bifonacci
Fibonacci numbers are defined as follows: f 0 = 0 , f 1 = 1 , and f n = f n − 1 + f n − 2 for n ≥ 2 .
How many pairs ( f m , f n ) , where f m and f n are Fibonacci numbers less than 1 0 8 , have the property that g cd ( f m , f n ) = 2 3 3 ?
Notation: g cd ( ⋅ ) denotes the greatest common divisor function.
The answer is 9.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Nice solution. Note that we could also find the value of m for which f m < 1 0 8 by using Binet's formula.
Please help me by identifying my error: F¹³ =233={((√5+1)/2)^13-((1-√5)/2)^13}/√5; Now multiplying both sides by n: {n∆^13-nß^13}/√5=233n. [∆=. {(√5+1)/2}^13, ß={(1-√5)/2}^13. ,And also ∆=-1/ß ]
Now,Let n∆^13=∆^k¹........(i) nß^13=ß^k².........(ii) Dividing these two equations: ∆^(13-k¹)=ß^(13-k²)=(-1/∆)^(13-k²); ∆^{26-(k¹+k²)}=(-1)^(13-k²);......(iii) Now,Multiplying (i) & (ii) and using ∆=-1/ß,we get: -n^2=(-1)^k².∆^(k¹-k²)......(iv) Putting the value of ∆^(k¹-k²) from eqn (iv) to eqn (iii): { ∆^26.(-1)^(k²-1)}/n^2=(-1)^(13-k²); ∆^26/n^2=(-1)^(14-2k²) =1 Giving n=∆^13; Now please tell me where is the wrong there??? please....hurry
Fibonacci number no. 13, 26, 39, ... are multiples of 233. Can you give a proof?
Log in to reply
just use the relation that I used in the solution. gcd(f(13),f(13t))=f(gcd(13,13t))=f(13)=233. so 233 should always divide f(13t) for all t
To Atomsky Jahid question, please read this proof .
I got stung by the fact that I did not know that the greatest common integer of 0 and a positive integer was defined and was that positive integer. I also forgot to apply the limitation of f m < = 1 0 8 and was using a larger set of Fibonacci numbers.
Firstly, the following fact, about Fibonacci numbers, is helpful.
g c d ( f m , f n ) = f g c d ( m , n )
Secondly, when f m < 1 0 8 , then m < 4 0 and this can be verified by having a look at Fibonacci numbers list.
Final fact is to realise that 2 3 3 = f 1 3
then we can get to the main Problem.
g c d ( f m , f n ) = f g c d ( m , n ) = 2 3 3 = f 1 3 ⟹ g c d ( m , n ) = 1 3
since m , n < 4 0 , the following pairs ( m , n ) would lead to g c d ( m , n ) = 1 3 ⟹ g c d ( f m , f n ) = 2 3 3
( 1 3 , 2 6 ) , ( 2 6 , 1 3 ) , ( 2 6 , 3 9 ) , ( 3 9 , 2 6 ) , ( 1 3 , 3 9 ) , ( 3 9 , 1 3 ) , ( 1 3 , 1 3 ) , ( 0 , 1 3 ) , ( 1 3 , 0 )