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