Author 
Topic: Fabonacci that shares a common factor (Read 4556 times) 

MUKAY
Newbie
Posts: 3


Fabonacci that shares a common factor
« on: Jun 21^{st}, 2012, 1:20pm » 
Quote Modify

Given a number M, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Fabonacci that shares a common factor
« Reply #1 on: Jun 22^{nd}, 2012, 8:39am » 
Quote Modify

Just compute the fibonacci sequence until gcd(f_i,M)!=1. Gcd is fast enough. To avoid large numbers, you can compute the f_i mod M. But you'll have to recompute the actual f_i afterwards.


IP Logged 



0.999...
Full Member
Gender:
Posts: 156


Re: Fabonacci that shares a common factor
« Reply #2 on: Jun 23^{rd}, 2012, 4:30am » 
Quote Modify

It's not obvious to me that every prime number is a factor of some Fibonacci number.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Fabonacci that shares a common factor
« Reply #3 on: Jun 23^{rd}, 2012, 1:32pm » 
Quote Modify

Well, you'd find quickly enough, because you're bound to repeat modulo M. So it's not like you'd go on forever. [e]From observation, it seem p divides F(p1) or F(p+1) (which isn't to say that's the first one)[/e] Aside from that, you bring a good idea to mind; using the prime decomposition of M and running Grimbal's algorithm on the distinct primes (rather than M) should generally be much faster.

« Last Edit: Jun 23^{rd}, 2012, 2:08pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



0.999...
Full Member
Gender:
Posts: 156


Re: Fabonacci that shares a common factor
« Reply #4 on: Jun 24^{th}, 2012, 6:14pm » 
Quote Modify

Ah, now I see that such a Fibonacci number must exist for every prime (the first iteration and therefore every one of the cycle mod p satisfies F_{k}(1)^{k+1}*F_{xk} where x is the length of a cycle). In fact, if x from the note above is a multiple of four then F_{x/2} can be divided by p. Combined with my conjecture that for every odd prime p different from 5, x is either p1 or 2(p+1) we have towr's observation.


IP Logged 



Saravana
Newbie
Gender:
Posts: 2


Re: Fabonacci that shares a common factor
« Reply #5 on: Jun 30^{th}, 2012, 1:04am » 
Quote Modify

How about calculating first fibonaci which has common divisor ( n= GCD(a,fi) ) and then calculating the GCD(n,2 <=x<=n ). That gives least common divisor between a fibonaci no and the given no(M)


IP Logged 



akasina9
Newbie
x = 0x2B  ~ 0x2B. x is the question
Gender:
Posts: 9


Re: Fabonacci that shares a common factor
« Reply #6 on: Nov 16^{th}, 2012, 12:04am » 
Quote Modify

on Jun 30^{th}, 2012, 1:04am, Saravana wrote:How about calculating first fibonaci which has common divisor ( n= GCD(a,fi) ) and then calculating the GCD(n,2 <=x<=n ). That gives least common divisor between a fibonaci no and the given no(M) 
 The question is about finding the lowest Fibonacci number, and not the lowest common divisor. your solution finds the lowest common divisor between the number found and the given number, which is not required at all. Consider M = 14. We'll get fi = 21, n = 7. Also, you'll get your lowest common factor as 7. But in fact the lowest common factor between 14 and and fibonaaci number is 2.


IP Logged 



