Author |
Topic: Fibonacci mod(m) (Read 1312 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Fibonacci mod(m)
« on: Feb 18th, 2006, 2:19am » |
 Quote  Modify
|
Show that the Fibonacci iteration taken modulo m :
Fk+1 = Fk + Fk-1 mod(m)
is periodic with period not exceeding 6m.
|
| « Last Edit: Feb 18th, 2006, 2:20am by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fibonacci mod(m)
« Reply #1 on: Feb 18th, 2006, 12:31pm » |
Quote Modify
|
Easy ... if m<=6. 
That F is periodic is simple enough. Any pair of adjacent Fibonacci numbers completely determines the rest of the sequence, so in particular, for the sequence of Fibonacci pairs Pn = (F2n, F2n+1), Pn+1 is completely determined by the value of Pn. So if Pn should ever take on a value a second time, it would necessarily fall into the same repeating loop. In turn this would mean that F must follow a repeating loop.
But in the case of F mod(m), there are only m2 possible values for Pn can take on. So somewhere in those first m2, Pn must start repeating.
Hence F mod(m) must be periodic with period <= 2m2.
A small tightening of the logic will show that F mod(m) has period <= m2.
To show that it is has period <= 6m, however, probably requires properties of the Fibonacci sequence itself, rather than just the fact that it is a 2nd order recursion.
|
|
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
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #2 on: Feb 19th, 2006, 4:43am » |
Quote Modify
|
Actually, by plotting the Fibonacci pairs (I used the definition Pn = (Fn, Fn+1), which is slightly different from Icarus' definition above) in a 2D plot and using different colours for the 'trajectories' traced from different starting values, one obtains interesting graphics.
Below picture show the case m=50. If you do a careful count, you will observe that no colour occurs more than 300 times... ).
[edit].... hmmm, seem unable to upload the picture..  [/edit]
[edit2] Hope this works:
... [/edit2]
|
| « Last Edit: Feb 19th, 2006, 6:44am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Fibonacci mod(m)
« Reply #3 on: Feb 19th, 2006, 6:47am » |
Quote Modify
|
Suppose xn is a sequence satisfying a second order recursion
xn+1 = axn + bxn-1,
and let A be the matrix
[ 0 1 ]
[ b a ].
Note that
[ 0 1 ] [xn-1] = [xn]
[ b a ] [xn] [xn+1].
It follows that the period of xn mod m will divide the order of A mod m, no matter what the initial values, provided A is invertible mod m. The only way this can happen for all m is if b = +/-1, which we'll therefore assume.
Conversely, if (x0, x1)=(0,1), then An is
[ bxn-1 xn ]
[ bxn xn+1 ],
and if (xn, xn+1)=(0,1) mod m, then xn-1= 1/b mod m, and so An = I mod m. Hence there exist initial values such that xn has period precisely the order of A.
If m=2, there are only two cases. If a=0, A has order 2, and if a=1, then A has order 3.
Now suppose m=p is an odd prime. Note that the characteristic polynomial of A is
t2 - at - b = (t - r)(t - s),
and we distinguish 3 cases according to the value of the discriminant d = a2+4b.
(1) d is a non-zero square mod p. Then the eigenvalues r,s are distinct elements of Zp*, and A is diagonalizable, so the order of A = lcm(order of r, s), which divides p-1.
(2) d is not a square mod p. Then A is diagonalizable, but the eigenvalues do not lie in Zp, but generate the degree 2 extension F=Zp(sqrt(d)). Now, the map f(x)=xp is an automorphism of F, whose fixed field is precisely Zp. It follows that rp=s, and sp=r. Then
rp+1 = sp+1 = rs = -b = -/+ 1,
and therefore the order of A divides 2(p+1).
(3) d=0 mod p. Then r=s, so A is not diagonalizable, and has the Jordan canonical form
[ r 1 ]
[ 0 r ],
whose n-th power is
[ rn nrn-1 ]
[ 0 rn ].
In this case the order of A is p*(order of r), which divides p(p-1).
Now, if k(pn) denotes the order of A mod pn, it follows from the claim at the end that k(pn) | pn-1k(p).
Finally, if m=p1e1...prer is a product of powers of distinct primes, then
k(m) = lcm(k(p1e1), ..., k(prer)) < lcm(pe1-1k(p1), ..., per-1k(pr)).
Now, k(2)=2 or 3. If (d|p)=1, then k(p) | p-1. If (d|p)=-1, then k(p) | 2(p+1). And if (d|p)=0 (which only happens for finitely many p), k(p) | p(p-1). Thus we have
k(m) < lcm( { k(2)2e-1 }, { (p-1)pe-1 }, { 2(p+1)pe-1 }, { p(p-1)pe-1 } )
< 4 * prod{3*2e-1} * prod1{ (p-1)/2 pe-1 } * prod-1{ (p+1)/2 pe-1 } * prod0 { p(p-1)pe-1 },
where the products are over the (possibly empty) sets of primes of each type. A term is present iff the corresonding e>0, in which case note that it is an integer, so the above is in fact a common multiple. Horrible notation aside, since (p-1)/(2p) < (p+1)/(2p) < 1 for all p, we have that in any case
k(m)/m < 4 * 3/2 * prodp|d (p-1) < 6|d|.
It follows that any sequence satisfying xn+1 = axn +/- xn-1 is periodic modulo m, with period at most 6|a2 +/- 4|*m. (I'm sure this bound can be improved.)
Back to the original problem: for the Fibonacci sequence, a=1, b=1, so d=5. In this case k(2)=3, and we have
k(m) < lcm( { 3*2e-1 }, { 4*5e }, { (p-1)pe-1 }, { 2(p+1)pe-1 } )
< 4 * {3/2*2e} * {5e} * prod{ (p-1)/(2p)pe} * prod{ (p+1)/(2p)pe }.
In any case, we have
k(m)/m < 4*(3/2) = 6.
In fact there is equality iff m=2*5e for some e>0. To see that m must be of this form, note that any prime p|m other than 2,5 contributes a factor <1 in the above, and lcm({3*2e-1}, {4*5f}) < 3*2e5f if e>1 or if f=0.
For the other direction, it suffices to show k(5e) = 4*5e for all e>0, for then
k(2*5e) = lcm(3, 4*5e) = 6*(2*5e). And therefore by the following claim it suffices to verify A20 != I mod 52. The claim generalizes the argument I gave in power shower (in fact, because it's more general, the proof must be simplified to not use cyclicity of (Z/pn)*.)
Claim: Let x be an integer, or more generally a square matrix with integer entries (or more generally, an element of a torsion-free Z-algebra, I guess). Let d(n) denote the order of x mod pn, for a prime p. Then d(n+1) is either d(n) or p*d(n). Moreover, if d(n)=p*d(n-1), and either p is odd or n>2, then d(n+1)=p*d(n).
Proof: First, since xd(n+1) = 1 mod pn+1, it certainly holds mod pn, so d(n) | d(n+1). Now, xd(n) = 1 + pny, so
xp*d(n) = 1 + pn+1y + p2np(p-1)/2 y2 + ... = 1 mod pn+1,
so d(n+1) | p*d(n), and the first part of the claim follows. Finally, if d(n)=p*d(n-1), then since xd(n-1) != 1 mod pn, we can write
xd(n-1) = 1 + pn-1y,
where y is not divisible by p. Then
xp*d(n-1) = 1 + pny + p2n-2p(p-1)/2 y2 + . . ..
If n>2, then 2n-2 > n+1, so the above is = 1+pny mod pn+1. Or, if n=2 and p is odd, then (p-1)/2 is an integer, and 2n-1 = 3, while k(n-1) >3 for k>3, so again the above is = 1 + p2y mod p3. But since y != 0 mod p, we have xd(n) != 1 mod pn+1, and so we must have d(n+1) = p*d(n).
|
| « Last Edit: Feb 19th, 2006, 6:57am by Eigenray » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #4 on: Feb 19th, 2006, 8:07am » |
Quote Modify
|
Wow... I already had the suspician you would quickly solve this problem, Eigenray. Well done!
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fibonacci mod(m)
« Reply #5 on: Feb 19th, 2006, 8:52am » |
Quote Modify
|
Very impressive, Eigenray! 
I just am not sure this solution (and this problem, by the way), is suited for the Medium section.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #6 on: Feb 19th, 2006, 1:35pm » |
Quote Modify
|
on Feb 19th, 2006, 8:52am, Barukh wrote:| I just am not sure this solution (and this problem, by the way), is suited for the Medium section. |
|
Yeah... I was in doubt whether to put it in 'hard' or not. But I figured there was a fair chance the problem would be solved in about 24 hrs.
And indeed... 
I try to follow the guiding principle that problems in the hard forum should be likely to require a collaborative effort and several days or weeks of iterations before the full solution emerges.
(Yes, I know... many problems in 'hard' don't satisfy this requirement...  )
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Fibonacci mod(m)
« Reply #7 on: Feb 19th, 2006, 10:40pm » |
Quote Modify
|
I was worried the solution might be too "mathy" for a medium thread, but it seemed the most natural way. There's another approach which may be more elementary. Recall that
Fn = 1/sqrt(5) [ ((1+sqrt(5))/2)n - ((1-sqrt(5))/2)n ]
= 2/2n [sum]k=0(n-1)/2 (nC2k+1) 5k.
Thus if p is an odd prime, then
Fp-1 = 2/2p-1 ( (p-1C1) + (p-1C3)5 + . . . + (p-1Cp-2)5(p-3)/2 )
= -2 ( 1 + 5 + ... + 5(p-3)/2 ),
since 2p-1=1, and (p-1Cr)=(-1)r mod p. Summing the geometric series,
Fp-1 = 1/2 ( 1 - 5(p-1)/2 ).
We also have
Fp = 2/2p ( (pC1) + ... + (pCp)5(p-1)/2 ) = 5(p-1)/2.
Note that since (5(p-1)/2)2 = 5p-1 = 1, we have 5(p-1)/2 = +/- 1. If we denote this expressian by (5|p), then in fact by quadratic reciprocity we have (5|p) = (p|5), which is +1 if p=+/-1 mod 5, and -1 if p=+/-2 mod 5. But this fact isn't necessary to solve the problem, only that it's +/-1 for any p != 2 or 5.
Now, suppose first (5|p)=1. Then Fp-1 = 0 = F0, and Fp = 1 = F1. It follows that Fn has period dividing p-1 in this case.
Suppose second that (5|p)=-1. Then Fp-1 = 1, and Fp = -1, so Fp+1 = 0, Fp+2 = -1. But recall the identity
Fi+j = Fi-1Fj + FiFj+1,
in which both sides are the i-th term of the Fibonacci-like sequence which starts Fj, Fj+1. From this we have
F2(p+1) = FpFp+1 + Fp+1Fp+2 = (-1)*0 + 0*(-1) = 0, and
F2(p+1)-1 = FpFp + Fp+1Fp+1 = (-1)2 + 02 = 1,
and we can conclude similarly the period of Fn divides 2(p+1).
For the case p=2, we can easily compute the period to be 3, and if p=5, then we have
Fn = n*3n-1,
which has period 5*4 = 20.
Finally, it remains to show k(pn+1) | pk(pn). This is most easily seen by the fact that
[ 0 1 ]n = [ Fn-1 Fn ]
[ 1 1 ] [ Fn Fn+1 ],
and using (I + pnB)p = I mod pn+1. Or, by using the above mentioned identity, we have
F(t+1)k = Fk-1Ftk + FkFtk+1,
F(t+1)k+1 = FkFtk + Fk+1Ftk+1,
from which we can prove inductively that if (Fk, Fk+1) = (0,1) mod pn, then
Ftk = t Fk, Ftk+1 = t(Fk+1-1)+1 mod pn+1,
and it follows (Fpk, Fpk+1) = (0,1) mod pn+1.
The rest, about maximizing k(m)/m, remains the same.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #8 on: Feb 23rd, 2006, 10:34am » |
Quote Modify
|
No-one who wonders why the picture of iterated Fibonacci pairs is the way it is..? 
[edit]linked to a copy of the picture stored without use of Google base[/edit]
|
| « Last Edit: Feb 26th, 2006, 2:15pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Fibonacci mod(m)
« Reply #10 on: Feb 23rd, 2006, 4:18pm » |
Quote Modify
|
Ah. There is indeed a picture hiding between Jock's [edit2] tags. Interesting. Could you explain exactly how that was made?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Fibonacci mod(m)
« Reply #11 on: Feb 23rd, 2006, 4:32pm » |
Quote Modify
|
a picture? where?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #12 on: Feb 24th, 2006, 8:51am » |
Quote Modify
|
on Feb 23rd, 2006, 4:18pm, Eigenray wrote:| Ah. There is indeed a picture hiding between Jock's [edit2] tags. Interesting. Could you explain exactly how that was made? |
|
For those who can't see the picture (have a look at my avatar...), you can create this 'Fibonacci recurrence plot' yourself as follows:
Start with a square m x m grid. (In above picture I used m = 50.) Cells in this grid have integer coordinates x = 0, 1, .. , m-1, y = 0, 1, .. , m-1. At start, all cells are empty (not coloured).
1) If all cells are coloured: stop. If not, select a cell (x0, y0) that is not coloured yet, and select a colour not utilised yet. Colour the cell with the selected colour.
2) compute the next cell using
xk+1 = yk
yk+1 = xk + yk (mod m)
3) if this cell is not coloured yet: colour this cell with the selected colour, and repeat step 2)
if this cell is already coloured, repeat step 1)
That's it...
|
| « Last Edit: Feb 24th, 2006, 11:41pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fibonacci mod(m)
« Reply #14 on: Feb 25th, 2006, 4:55pm » |
Quote Modify
|
Curious. I could not see it or find it no matter what I did. Even SMQ's link gave me a 404 error.
Until I viewed the page source like he said and found the link in it (search the source for the text "edit2" - the link is just after). I pasted that link into the address box, and it brought up the picture. (Curious that SMQ's link didn't work, since the address is the the same!) But now the same picture loads up and shows just fine in Jock's post. It continues to show up even after closing and reopening the browser.
Anyone have an idea what is going on?
|
|
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
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #15 on: Feb 25th, 2006, 6:22pm » |
Quote Modify
|
on Feb 25th, 2006, 4:55pm, Icarus wrote:| Anyone have an idea what is going on? |
|
No idea, but can tell you SMQ's link works fine for me. And I can see both copies of the picture that I posted in this thread (in my posts of 19/2 and 23/2). The same picture also shows as my avatar.
I also tried to log off from the forum and to view the pictures in this thread as a guest. Made no difference, all pictures are there.
A thing that doesn't work for me is that I no longer can upload gif/jpg files as attachment to a message (that's why I placed the picture on the web and utilised picture links).
Note that the picture on Google base is not a jpg or gif file. Could that make a difference?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Fibonacci mod(m)
« Reply #16 on: Feb 25th, 2006, 8:49pm » |
Quote Modify
|
on Feb 25th, 2006, 4:55pm, Icarus wrote:| Anyone have an idea what is going on? |
|
Google must be doing things with the "Referrer" header field (which tells a web server what page you're coming from) to prevent embedding Google Base links in non-Google pages. Even following he link from this page seems to trigger their "security" measures. With a cut-and-paste there's no referring page and so it works as expected... (and since JocK, being the content creator, has the appropriate Google Base cookies, he can see it all the time.)
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Fibonacci mod(m)
« Reply #17 on: Feb 26th, 2006, 1:41pm » |
Quote Modify
|
Oddly, however, having successfully visited the site by cut and paste, I can now follow the link without the problems I had before.
But even more, I no longer need to. Just like Jock, I now see both of his postings of the picture, whereas before, there was no indication at all that a picture was supposed to be in either one (other than Jock's contextual comments).
|
|
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
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Fibonacci mod(m)
« Reply #18 on: Feb 26th, 2006, 2:25pm » |
Quote Modify
|
on Feb 26th, 2006, 1:41pm, Icarus wrote:Oddly, however, having successfully visited the site by cut and paste, I can now follow the link without the problems I had before.
But even more, I no longer need to. Just like Jock, I now see both of his postings of the picture, whereas before, there was no indication at all that a picture was supposed to be in either one (other than Jock's contextual comments). |
|
Must be because the cookies SMQ mentioned are now available on your computer.
Can you see my Avatar? (I start doubting the visibility of all pictures I see after loading them myself.. )
Link to the problem + picture on Google Base:
http://base.google.com/base/items?customerId=1121639&offerId=6838743 187121338456
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fibonacci mod(m)
« Reply #19 on: Feb 28th, 2006, 4:40am » |
Quote Modify
|
I would like to go back from access and visibility problems (BTW, I personally do see JocK’s beautiful avatar) to the question posted by JocK. I apologize if I repeat some arguments mentioned previously in this thread.
It is clear that every color in the picture represents a Fibonacci-like sequence {Gn} with G0 = x0 and G1 = y0. Let k(m) be the period of Fibonacci sequence Fn modulo m, and h(m) the period of the sequence Gn modulo m. Since Gn = G0Fn-1 + G1Fn, it follows that h(m) | k(m). Therefore, any color cannot occur more than 6m times – as stated by JocK and proved (twice) by Eigenray.
Next, I will consider the sequences with G0 = 0 (all the operations are modulo m). Let d > 0 be the smallest number such that Gd = 0. Clearly, d <= h(m). If d < h(m), then we have
Gd+1 = Gd-1,
Gd+2 = Gd+1 + Gd = Gd+1 – 0 = Gd+1 - Gd-1 - Gd-2 = -Gd-2,
and by induction show that Gd+n = (-1)n+1Gd-n. Therefore, G2d = 0, and d | h(m). I am now going to consider 3 possible cases:
1. d = h(m) (e.g. m = 11). In this case, I wouldn’t expect any symmetry for this particular color.
2. d < h(m), d even (e.g. m = 47). Then, G2d+1 = G2d-1 = G1, therefore, h(m) = 2d. In this case, if point (x, y) is colored, then one of the points (y, -x) or (-y, x) is also colored. I don’t see any particular symmetry in this case too.
3. d < h(m), d odd (e.g. m = 10). Then, G2d+1 = -G1, G3d+1 = G3d-1 = -Gd+1 != 1, but G4d+1 = G1, therefore h(m) = 4d. In this case, each of the 4 points P1(x, y), P2(-y, x), P3(-x, -y), P4(y, -x) will have the same colour. Note, that vectors P1 - P3 and P2 - P4 are orthogonal and have the same length, meaning the four points are the vertices of a square!
Now, in JocK's avatar, m = 50, and d = 75. Thus the mentioned symmetry.
Any comments? 
P.S. This doesn’t explain why there is an apparent symmetry for the sequences with G0 != 0.
|
| « Last Edit: Feb 28th, 2006, 4:51am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
