fibonacci residues, mod m
quasi
Fibonacci numbers, I wrote a few Maple test programs just to answer a
some preliminary questions. Each question led to new questions. Based
on the explorations, I came up with a few conjectures. Of course, it's
likely that these questions have already been studied, but I'm not
sure. In any case, here are the conjectures ...
Conjecture (1):
If m is a positive integer with a prime factor greater than 7, then
the Fibonacci numbers do not give all residues mod m.
Conjecture (2):
There exist inifinitely many positive integers m such that the
Fibonacci numbers give all residues mod m..
quasi
Larry Hammick
#2 looks like the Artin Conjecture that nobody has any idea how to prove:
Any nonsquare n>1 is a generator of Z/pZ for infinitely many primes p. (The
special case n=10 goes back to Gauss; neither that case nor any other case
has yet been settled AFAIK.)
#1 is true: If a prime p is 1 or -1 mod 10, then f_{p-1} is a multiple of p
and f_p is 1 mod p, and therefore the sequence is period mod p, with period
p-1 or less, whence the conclusion.
Larry Hammick
Oops, damn, that's not the whole answer to (1). Still looking.
LH
quasi
<larryh...@telus.net> wrote:
>"quasi"
>> In trying to solve the problem tommy1729 recently posed concerning
>> Fibonacci numbers, I wrote a few Maple test programs just to answer
>> some preliminary questions. Each question led to new questions. Based
>> on the explorations, I came up with a few conjectures. Of course, it's
>> likely that these questions have already been studied, but I'm not
>> sure. In any case, here are the conjectures ...
>>
>> Conjecture (1):
>>
>> If m is a positive integer with a prime factor greater than 7, then
>> the Fibonacci numbers do not give all residues mod m.
>>
>> Conjecture (2):
>>
>> There exist inifinitely many positive integers m such that the
>> Fibonacci numbers give all residues mod m.
>>
>> quasi
>
>#2 looks like the Artin Conjecture that nobody has any idea how to prove:
>Any nonsquare n>1 is a generator of Z/pZ for infinitely many primes p. (The
>special case n=10 goes back to Gauss; neither that case nor any other case
>has yet been settled AFAIK.)
Can you give more explanation as to how the Artin conjecture relates
(and possibly subsumes) my conjecture (2)? I don't quite follow. Also,
I note you are only considering primes p, rather than arbitrary
positive integers m. Is it obvious how to reduce conjecture (2) for
arbitrary m to the case where m is prime?
>#1 is true: If a prime p is 1 or -1 mod 10, then f_{p-1} is a multiple of p
>and f_p is 1 mod p, and therefore the sequence is period mod p, with period
>p-1 or less, whence the conclusion.
Here too, I don't quite follow.
As far as I can see, your argument proves a lot less than conjecture
(1).
If I understand the argument correctly, you show that if the fibonacci
sequence represents all residues mod m, then m cannot be a prime which
is congruent to 1 or -1 mod 10.
How does that show that all prime factors of m must be elements of the
set {2,3,5,7}?
quasi
Larry Hammick
news:3tj093lo4slpg4jko...@4ax.com...
> On Sun, 08 Jul 2007 01:35:12 GMT, "Larry Hammick"
> <larryh...@telus.net> wrote:
>
>>"quasi"
>>> In trying to solve the problem tommy1729 recently posed concerning
>>> Fibonacci numbers, I wrote a few Maple test programs just to answer
>>> some preliminary questions. Each question led to new questions. Based
>>> on the explorations, I came up with a few conjectures. Of course, it's
>>> likely that these questions have already been studied, but I'm not
>>> sure. In any case, here are the conjectures ...
>>>
>>> Conjecture (1):
>>>
>>> If m is a positive integer with a prime factor greater than 7, then
>>> the Fibonacci numbers do not give all residues mod m.
>>>
>>> Conjecture (2):
>>>
>>> There exist inifinitely many positive integers m such that the
>>> Fibonacci numbers give all residues mod m.
>>>
>>> quasi
>>
>>#2 looks like the Artin Conjecture that nobody has any idea how to prove:
>>Any nonsquare n>1 is a generator of Z/pZ for infinitely many primes p.
>>(The
>>special case n=10 goes back to Gauss; neither that case nor any other case
>>has yet been settled AFAIK.)
>
> Can you give more explanation as to how the Artin conjecture relates
> (and possibly subsumes) my conjecture (2)?
Just that the Fibo sequence behaves roughly like an exponential, not just in
its rate of growth, but in its arithmetic properties.
>>#1 is true: If a prime p is 1 or -1 mod 10, then f_{p-1} is a multiple of
>>p
>>and f_p is 1 mod p, and therefore the sequence is period mod p, with
>>period
>>p-1 or less, whence the conclusion.
>
> Here too, I don't quite follow.
>
> As far as I can see, your argument proves a lot less than conjecture
> (1).
True. I blundered. I mis-thought that the aim was to show that there are
infinitely m for which the sequence is not surjective mod m. (There are
infinitely primes 1 mod 10 or -1 mod 10 okay.) I think I can push through to
a proof for primes m>7 which are 3 or 7 mod 10, so it'll be proved for all
primes >7, but I don't have an idea for the composite cases.
LH
quasi
<larryh...@telus.net> wrote:
Wait -- the composite case trivially reduces to the prime case. I just
wasn't thinking when I suggested that wasn't obvious.
If a set of numbers doesn't represents all numbers mod m, then it
doesn't represent all numbers mod (any nonzero multiple of m).
Thus, if you prove that there are no primes greater p than 7 for which
the Fibonacci numbers represent all residues mod p, then the same is
true for m where m is any multiple of p.
That would then clinch conjecture 1.
Thus, for conjecture 1, It looks like the proof strategy you outlined
may work just fine.
quasi
Robert Israel
> In trying to solve the problem tommy1729 recently posed concerning
> Fibonacci numbers, I wrote a few Maple test programs just to answer a
> some preliminary questions. Each question led to new questions. Based
> on the explorations, I came up with a few conjectures. Of course, it's
> likely that these questions have already been studied, but I'm not
> sure. In any case, here are the conjectures ...
>
> Conjecture (1):
>
> If m is a positive integer with a prime factor greater than 7, then
> the Fibonacci numbers do not give all residues mod m.
Case 1. Suppose 5 is a square mod p, where p is an odd prime (<> 5),
say s^2 == 5 [== will mean congruent mod p in the following]. Then
the Fibonacci numbers mod p can be written as
f_n == (a^n - (1-a)^n)/s where a == (1+s)/2.
By Little Fermat, a^(p-1) == (1-a)^(p-1) == 1 so f_{p-1} == 0 and
f_p = 1, and so f_n mod p is periodic with period at most p-1; there are
at most p-2 different values (since f_2 = f_1 = 1).
Case 2. Suppose 5 is not a square mod p. By considering a field
extension of Z_p in which 5 does have a square root, it can be shown
that f_{p+1} == 0, f_p == f_{p+2} == -1, f_{2p+2} == 0 and
f_{2p+1} = f_{2p+3} == 1. Thus the sequence f_n has period at most 2p+2.
Moreover, f_{n+p+1} == -f_n while f_{p+1-n} == (-1)^n f(n) and
f_{2p+2-n} == (-1)^(n+1) f(n). This _almost_ rules out the possibility
of covering all residues mod p, as each f_n will occur at least twice
in {f_j: j = 0 .. 2p+1} (both as f_n and as either f_{p+1-n} or f_{2p+2-n} or
f_{3p+3-n}) while 1 == f_1 == f_2 == f_{p-1} == f_{2p+1} and
-1 == f_p == f_{p+2} == f_{p+3} == f_{2p} occur at least 4 times each.
That would make a total of at least 2(p-2) + 8 = 2p+4 > 2p+2.
It doesn't quite work because f_{(p+1)/2} and f_{3(p+1)/2}
could just occur once. Indeed this happens for p = 7, where
the sequence f_n mod 7 starts 0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1
and 3 == f(4) and 5 == f(12) are not duplicated. If p is congruent
to 1 mod 4, this won't happen, because f((p+1)/2) == 0. If p is
congruent to 3 mod 4, I don't see a way to rule it out.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada V6T 1Z2
quasi
Very nice analysis.
It appears that you've partially proved my conjecture (1). More
specifically, you've proved it for all positive integers m having at
least one prime factor p such that p>7 and p is not congruent to 3 mod
4. Is that a correct summary?
Thus, conjecture (1), though weakened, appears to have survived
attacks by both Larry Hammick and Robert Israel. I'm satisfied with
that!
But, while conjecture (1) is clearly hanging on by only a thread,
conjecture (2) appears out of reach, taunting us, boasting of its
invulnerability.
quasi
Larry Hammick
"quasi" <qu...@null.set> wrote in message
I haven't thoroughly checked all the following but I'll toss it out there
nonetheless.
Say p=10+3 is prime. We have (all equations mod p)
f(p+1) = 0
f(p+2) = -1
and so
f(n+p+1) = -f(n) for all n
and so
f(n+2p+2) = f(n)
i.e. f is periodic with period 2p+2 = 20n +8 at the most. We want to show
that of the 20n+8 initial values of f there are only 10n+2 or fewer distinct
ones, ie. we want to find 10n+6 duplications. Here are some:
f(2p+1-2s) = f(2s+1) for 0 <= s <= 5n+1
f(p-1-2s) = f(2s+2) for 0 <= s <= floor[5n/2]
f(2p-2s) = f(p+3+2s) for 0 <= s <= floor[5n/2].
We've found so far at least
(5n+2) + 1+(5n-1)/2 + 1+(5n-1)/2
which is 10n+3. We need 3 more. Voila:
f(1) = 1 = f(2)
f(0) = 0 = f(p+1)
f(p) = -1 = f(p+2).
The case p = 10n+7 is not much different.
LH
Oscar Lanzi III
Let p be a prime ending with 3 or 7 in base 10 and greater than 3 (the
latter restriction is imposed for reasons that will become evident in
the proof). For future reference, the set of all such primes is
designated as D. Based on previous postings in this thread all primes
for which the conjecture has remained open are in D.
For every prime p in D, the Fibonacci sequence has period 2p+2 mod p,
meaning F(2p+2) == F(0) = 0 (all congruences are mod p). The sequence
may also have a smaller period of p+1, but whether it does or not F(p+1)
must also have residue 0. This is because of the symmetry relation,
Eq. (1), which holds for all k when F(m) == 0:
F(m-k) == (-1)^(k-1)*F(m+k) ... Eq. (1)
With m = 2p+2 and k = p+1, an even number, this implies F(3p+3) ==
-F(p+1), but by periodicity F(3p+3) == +F(p+1). Therefore F(p+1) ==
0.
Since F(0) == F(p+1) == 0 and F(1) = 1, we must have F(p+1+k) ==
F(p+2)*F(k) and thus F(2p+2+k) == (F(p+2))^2*F(k). Because of
periodicity this implies that F(p+2) must be either +1 or -1 mod p, and
therefore
F(p+1+k) == (+/-) F(k) ... Eq. (2)
Apply Eq. (1) again with m = p+1; then by Eqs. (1) and (2):
F(p+1-k) == (-1)^(k-1)*F(p+1+k) == (+/-) F(k) ... Eq. (3)
Squaring Eqs. (2) and (3) leads to the following:
(F(k))^2 == (F(p+1-k))^2 = (F(p+1+k))^2 = (F(2p+2-k))^2 ... Eq. (4)
Eq. (4) says that throughout any period of the Fibonacci sequence mod p,
the squared Fibonacci numbers (F(k))^2 with k form 0 through (p+1)/2
contain all the quadratic residues mod p that appear in the squares of
Fibonacci numbers. It follows that (p+1)/2 out of these (p+3)/2
residues must be distinct if every residue is to occur in the unsquared
Fibonacci numbers. But perforce F(1) == F(2) because both are equal
to 1. Therefore, all other quadratic residues in this set must be
distinct from each other and from 1 mod p. In particular, all of the
(p-1)/2 quadratic residues from (F(2))^2 to (F((p+1)/2))^2 must be
distinct and nonzero.
The last statement implies that the following summation must hold if p
is in D and all residues mod p appear in the Fibonacci sequence:
Sum((F(k)^2, k = 2 to (p+1)/2) == (p^2-1)*p/24 == 0 ... Eq. (5)
The second member in the equation is a multiple of p whenever p^2-1 is a
multiple of 24, which is true for all p > 3 and thus for all p in D.
Eq. (5) must be checked against the actual value of the sum on its left
side, which is hereafter designated as S. If, for example, Eq. (5) is
tested for p = 13, we find that S is 272, which has residue 12 (or -1)
instead of 0 mod 13. This is because the numbers (F(k))^2 for k = 2,
3, 4, 5, 6, 7 do not have all distinct nonzero quadratic residues mod 13
(specifically, F(5) and F(6) have congruent squares, and (F(7))^2 ==
0). This inequality in interpreted to mean that in mod 13, there must
be some missing residues in the Fibonacci sequence according to the
paragraph following Eq. (4). These prove to be 4, 6, 7, and 9, whose
squares are the missing quadratic residues (3 and 10) in S for p = 13.
S is simplified using the identity (F(k-1))^2 + (F(k))^2 = F(2k-1) =
F(2k-3) + F(2k-2). Thus:
(F(2))^2 + (F(3))^2 = F(5) = F(3) + F(4)
(F(3))^2 + (F(4))^2 = F(7) = F(5) + F(6)
(F(4))^2 + (F(5))^2 = F(9) = F(7) + F(8)
.
(F((p-1)/2)^2 + (F((p+1)/2)^2 = F(p) = F(p-2) + F(p-1)
Summing the first terms on the left side gives S - (F((p+1)/2))^2;
summing the second terms on the left side gives S - (F(2))^2 = S -1, and
summing the right side gives
T = Sum(F(k), k = 3 to p-1) = F(p+1) ? F(4) == -3
Therefore, 2S - (F(p+1)/2))^2 ? 1 == -3, and Eq. (5) then implies
(F((p+1)/2))^2 == 2 ... Eq. (6)
Eq. (6) would appear to be satisfied for many primes p, but that is not
so.
Eq. (3) with k = 1 implies
F((p-1)/2) == (+/-)F((p+3)/2) ... Eq. (7)
Combining this with the standard Fibonacci recurrence relation then
gives:
F((p+1)/2) == (1 - (+/-) 1))*F((p+3)/2) ? Eq. (8)
The right side of Eq. (8) is zero when the (+/-) sign is positive,
contradicting Eq. (6). Accordingly the (+/-) sign in Eq. (7) must be
negative. Then Eqs. (7) and (8) become:
F((p-1)/2) == -F((p+3)/2) ... Eq. (9)
F((p+1)/2) == 2*F((p+3)/2) ... Eq. (10)
If Eq. (10) is squared and then combined with Eqs. (6) and (9), one
obtains the result:
2*F((p-1)/2)* F((p+3)/2) == -1 ... Eq. (11)
Lastly the following is applied:
(F(k))^2 ? F(k-1)*F(k+1) = (-1)^(k-1) ... Eq. (12)
Multiplying Eq. (10) by 2 with k = (p+1)/2 and applying the congruences
from Eqs. (6) and (11) gives:
4 + 1 == 2*(-1)^((p-1)/2) ... Eq. (13)
If p is a 4n+1 prime, the right side of Eq. (13) is 2 and the equation
has no solution consistent with p being a 4n+1 prime. If p is a 4n-1
prime, the right side of Eq. is -2, in which case Eq. (11) has only the
solution p = 7. Therefore the _only_ p in D (in fact, the _only odd
prime_) that solves Eq. (6) is p = 7. It follows that for all p in D
except 7, Eq. (5) cannot hold and, therefore, the Fibonacci numbers
cannot include all residues mod p.
--OL