Newsgroups: sci.math From: lung@pinatubo.issy.cnet.fr (Frederic Lung) Subject: Fibonnaci conjecture Keywords: Fibonnaci 'prime number' Date: Wed, 7 Feb 1996 10:17:03 GMT Can anyone help prove the following conjecture involving the main Fibonacci sequence and certain prime numbers? This conjecture can be expressed in three equivalent ways, and proving any one is sufficient. Given f(n), the main Fibonacci sequence: f(0) = 0; f(4) = 3; f(8) = 21; f(1) = 1; f(5) = 5; f(9) = 34; f(2) = 1; f(6) = 8; f(10) = 55; f(3) = 2; f(7) = 13; ... and p, a prime number different from 2 or 5. Here are the three ways: 1) The smallest value that is divisible by p is never divisible by p**2 (p raised to the power of 2). Example: f(9) is divisible by 17, but is not divisible by 17**2 (=289). 2) If the last digit of p is 3 or 7, then f(p + 1) is divisible by p (this is already proved) but is not divisible by p**2. Similarly, if the last digit of p is 1 or 9, then f(p - 1) is divisible by p (already proved) but is not divisible by p**2. Examples: For p=7, f(8) (=21) is divisible by 7 but not by 49. For p=11, f(10) (=55) is divisible by 11 but not by 121. 3) If f(n) is divisible by p**2 then n is divisible by p. I'm posting this article for the author of this conjecture, my friend Max de Ferran. Thank you in advance. Frederic Lung ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Fibonnaci conjecture Date: 7 Feb 1996 19:15:43 GMT Keywords: Fibonnaci 'prime number' In article <1996Feb7.101703.21698@cnet.fr>, Frederic Lung wrote: >Given f(n), the main Fibonacci sequence: [1, 1, 2, 3, 5, ... starting with n=1] ... [and] > p, a prime number different from 2 or 5. ... >1) The smallest value that is divisible by p is > never divisible by p**2 (p raised to the power of 2). I would be very surprised if anyone could prove this. The n-th Fibonacci number is (r^n-s^n)/sqrt(5) where r = (1+sqrt(5))/2 and s= (1 - sqrt(5))/2. For p other than 5, this is a multiple of p iff r^n-s^n is (in the ring Z[sqrt(5)]); since s is a unit in this ring, this is equivalent to having (r/s)^n = 1 mod p, so that n is a multiple of the order of a=(3+sqrt(5))/(-2) in the multiplicative group of Z[sqrt(5)]/p. The order g of this group is either p^2-1 or (p-1)^2, depending on the residue of p mod 5, so by Lagrange's theorem, we certainly know that the smallest such n is a divisor of g . Likewise, the assertion that f(n) is divisible by p^2 is equivalent to a^n = 1 mod p^2. Note that if a^n = 1 + wp then a^(nm) = 1 + (wm)p mod p^2, so that a^n = 1 mod p^2 iff a^g = 1 mod p^2. So the question is simple: you take a very specific algebraic integer a, raise it to a specific power g which you are certain will give an integer congruent to 1 mod p, and ask whether it happens to be congruent to 1 mod p^2. Unfortunately, this question admits no easy answer (at least none yet known). This is essentially the same question as asking whether 2^(p-1) = 1 mod p^2 or 5^(p-1) = 1 mod p^2, say, has any solutions in primes p. This question attained a certain importance when it was established around the turn of the century that the "first case" of Fermat's Last Theorem is true of any prime p not satisfying these equations. An exhaustive search reveals that 2^1093 = 1 mod 1093^2 and 2^3510=1 mod 3511^2, but no other solutions exist for p less than, oh, 100 000 perhaps. Naturally one begins to conjecture that there are no other solutions, but there is no method known which can answer this question. Conceivably, of course, your a is special enough that one can determine whether a^g = 1 mod p^2 more certainly than one can determine that 2^g = 1 mod p^2. But, as I say, I would be very surprised. dave