Author |
Topic: Periodic Fibonacci (Read 894 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Periodic Fibonacci
« on: Mar 22nd, 2006, 8:07pm » |
 Quote  Modify
|
True or False:
Let {fn} be the Fibonacci series (f1 = f2 = 1, fn+1 = fn + fn-1). For any positive integer q, if k is the smallest index for which q | fk (q divides fk), then q | fn if and only if k | n.
|
| « Last Edit: Mar 22nd, 2006, 8:09pm by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Periodic Fibonacci
« Reply #1 on: Mar 23rd, 2006, 5:51am » |
Quote Modify
|
I think I tried to show this here?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #2 on: Mar 23rd, 2006, 2:47pm » |
Quote Modify
|
Similar, but it does not appear to be the same thing to me.
I will say, however, that almost immediately after posting this, I realized that it is nearly trivial if approached from the right direction.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Periodic Fibonacci
« Reply #3 on: Mar 24th, 2006, 11:52am » |
Quote Modify
|
Since f0=0, it follows that k is the period of q. Hence q | fn if and only if k | n.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #4 on: Mar 24th, 2006, 3:14pm » |
Quote Modify
|
That is just restating the problem. It is not a proof of anything.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #5 on: Mar 24th, 2006, 4:05pm » |
Quote Modify
|
Sorry. I now realize you were building off the result of the other thread. But it doesn't follow necessarily that k is the period of q. For example, consider the periodic sequence
0 1 2 0 3 4 0 1 2 0 3 4 0 ...
Besides which, you can prove this whole result much more easily than the proof in the other thread (which adds size requirements to k, but lacks the "only if" portion of this one).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Periodic Fibonacci
« Reply #6 on: Mar 24th, 2006, 6:25pm » |
Quote Modify
|
I spoke too soon. Certainly, q can divide a term in the middle of the period of the sequence. Sorry, Icarus. q=5 illustrates this:
1 1 2 3 0 2 2 4 1 0 1 ... (mod 5)
The period is 10 yet still divisible by k=5.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Periodic Fibonacci
« Reply #7 on: Mar 25th, 2006, 5:39am » |
Quote Modify
|
True. First a little lemma.
If q | f(m), then f(m+1)=f(m+2)=a (mod q), for some integer a; whence f(s+m)=af(s) (mod q), for all s[ge]0.
So, when m=s=k, q | f(2k). When m=k and s=2k, q | f(3k), etc.
Conversely, let p be a divisor of q and a. Then the lemma implies that p divides all f(t), for all t[ge]m modulo q. Since f is periodic modulo q, it follows that p divides f(1)=1 modulo q; so p=1. But then the shortest interval between terms divisible by q is k. Now let q | f(n) and set n=ku+r, with 0[le]r<k. Then q divides f(ku) and f(n), so r=0 and k | n.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #8 on: Mar 25th, 2006, 8:29am » |
Quote Modify
|
That is in essense the proof I found, and if you are familiar with the properties of the cyclic groups Zq, it is almost trivial when stated in those terms. The essential artifact is that adjacent elements of the Fibonacci sequence are always relatively prime (anything that divides both fn+1 and fn must also divide fn-1 = fn+1 - fn, and by induction, must also divide f1 = 1).
In fact, we can generalize to result to many other recursive sequences. Say that the sequence Fn has the "index-divisor property for q" if q | Fn if and only if k | n, where k is the smallest index > 0 for which q | Fk.
Lemma: If P(x, y) is a polynomial and Fn is an integer sequence satisfying the recursion relation Fn+1 = P(Fn, Fn-1), and if Fn has the property that any two adjacent elements are relatively prime, then Fn has the index-divisor property for all divisors q of F0.
Proof: Consider the sequence Gn = Fn mod q in Zq. G0 = Gk = 0, and G1 and Gk+1 must both be generators of Zq, since F1 and Fk+1 are both relatively prime to q. Therefore there is an automorphism h of Zq which carries G1 to Gk+1, and also h(G0) = 0 = h(Gk). Now if h carries Gn and Gn+1 to Gn+k and Gn+k+1 respectively, then
h(Gn+2) = h(P(Gn+1, Gn)) = P(h(Gn+1), h(Gn)) = P(Gn+k+1, Gn+k) = Gn+k+2.
So by induction, h(Gn) = h(Gn+k) for all n >= 0. Since h(x) = 0 if and only if x = 0, and since k is the smallest index for which Gk = 0, the conclusion follows.
Corrolary: If P(x, y) is a polynomial with integer coefficients, and if Fn is a sequence with F0 = 0, GCD({Fn}) = 1, and which satisfies the recursion Fn+1 = P(Fn, Fn-1)Fn + Fn-1, then Fn has the index-divisor property for all integers q.
Proof: Since Fn-1 = Fn+1 - P(Fn, Fn-1)Fn, any common divisor p of Fn+1 and Fn also divides Fn-1, and by the forward recursion formula, it must also divide Fn+2. By induction, p must divide Fm for all m, and hence must be 1. Thus all adjacent elements of Fn are relatively prime, and since every integer other than zero divides F0 = 0, the corrolary follows. (q=0 works because there is no index k for which q | Fk.)
_________________________________________________
I find this an extraordinary property, that divisors enter the Fibonacci sequence in such a regular fashion, and I think it goes a long way towards explaining the pattern in Jock's new avatar.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Periodic Fibonacci
« Reply #9 on: Mar 25th, 2006, 6:27pm » |
Quote Modify
|
If F is the matrix
[ 0 1 ]
[ 1 1 ],
then Fn =
[ fn-1 fn ]
[ fn fn+1 ].
This gives a rather concise proof: q|fn iff Fn is a scalar matrix mod q, so k is simply the order of F in the group PGL2(Zq). (That is, the quotient of GL2(Zq), the group of invertible 2x2 matrices over the ring Zq, by the (central) subgroup of scalar matrices.)
on Mar 25th, 2006, 8:29am, Icarus wrote:G0 = Gk = 0, and G1 and Gk+1 must both be generators of Zq, since F1 and Fk+1 are both relatively prime to q. Therefore there is an automorphism h of Zq which carries G1 to Gk+1, and also h(G0) = 0 = h(Gk). Now if h carries Gn and Gn+1 to Gn+k and Gn+k+1 respectively, then
h(Gn+2) = h(P(Gn+1, Gn)) = P(h(Gn+1), h(Gn)) = P(Gn+k+1, Gn+k) = Gn+k+2. |
|
To commute with polynomials you need h to be a ring automorphism, and Zq just doesn't have that many.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #10 on: Mar 26th, 2006, 11:53am » |
Quote Modify
|
on Mar 25th, 2006, 6:27pm, Eigenray wrote:| To commute with polynomials you need h to be a ring automorphism, and Zq just doesn't have that many. |
|
You're right. I should of thought about that a little more closely. The result still holds for all recursions of the form Fn+1 = AFn + Fn-1, but I was mistaken in believing it held for more general ones.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Periodic Fibonacci
« Reply #11 on: Jul 25th, 2006, 11:59am » |
Quote Modify
|
Not entirely true. The original question doesn't hold for k=2. Seems to work after that, though.
My solution [ed] which now I see is the same as ecoist's [/ed]:
First of all, note that f0=0 is divisible by any number. Now look at the fibonacci sequence in modulo q arithmetic. The sequence starts off with 1 1 , follows with a sequence of numbers that are not equal to q, and then a zero. For instance (q = 17):
1 1 2 3 5 8 13 4 0
Now what happens after the zero? The next numbers are 4 and 4, so we therefore get the same sequence multiplied by a constant. For a prime number q, multiplying any two non-zero numbers smaller than q by a constant will not give you a multiple of q. Therefore, the second sequence will return to zero only at the point the first sequence returned to zero, which is to say it will have the same length, which proves the point.
For a composite q, we must show that the number immediately before the zero (call it m) does not share any factors with q, or the multiplication in the above step could lead to premature zeros. This is simple to show. Suppose gcf(m,q) = n, and note that zero is also divisible by n. Subsequent numbers in the sequence are formed by adding multiples of n, and possibly subtracting q (also a multiple of n). These operations will always produce multiples of n. However, a simple finiteness argument shows us that that the modulo fibonacci sequence repeats itself, so we know that the number 1 must show up again. Therefore the only possible n is 1.
|
| « Last Edit: Jul 25th, 2006, 12:03pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Periodic Fibonacci
« Reply #12 on: Jul 25th, 2006, 2:25pm » |
Quote Modify
|
on Jul 25th, 2006, 11:59am, James Fingas wrote:| Not entirely true. The original question doesn't hold for k=2. |
|
You get to pick q, not k. For q=1, k=1; and for q>1, k>2. k = 2 never comes up.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print