wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Fibonacci mod(m)
        
(Message started by: JocK on Feb 18th, 2006, 2:19am)
Title: Fibonacci mod(m)
Post by JocK on Feb 18th, 2006, 2:19am
Show that the Fibonacci iteration taken modulo m :

Fk+1 = Fk + Fk-1 mod(m)

is periodic with period not exceeding 6m.
Title: Re: Fibonacci mod(m)
Post by Icarus on Feb 18th, 2006, 12:31pm
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.
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 19th, 2006, 4:43am
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:
http://base.google.com/base_image?q=hand7941761016343606377&size=6
... [/edit2]
Title: Re: Fibonacci mod(m)
Post by Eigenray on Feb 19th, 2006, 6:47am
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 [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1138904859]power shower[/link] (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).
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 19th, 2006, 8:07am
Wow... I already had the suspician you would quickly solve this problem, Eigenray. Well done!
Title: Re: Fibonacci mod(m)
Post by Barukh on Feb 19th, 2006, 8:52am
Very impressive, Eigenray!  :D

I just am not sure this  solution (and this problem, by the way), is suited for the Medium section.
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 19th, 2006, 1:35pm

on 02/19/06 at 08:52:40, 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...  ;D

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...  :( )
Title: Re: Fibonacci mod(m)
Post by Eigenray on Feb 19th, 2006, 10:40pm
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.
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 23rd, 2006, 10:34am
No-one who wonders why the picture of iterated Fibonacci pairs is the way it is..?  :o

http://sc.groups.msn.com/tn/20/42/ko-bridge/5/20.jpg


[edit]linked to a copy of the picture stored without use of Google base[/edit]
Title: Re: Fibonacci mod(m)
Post by towr on Feb 23rd, 2006, 2:08pm
Show me the picture, and maybe I'll wonder :P
Title: Re: Fibonacci mod(m)
Post by Eigenray on Feb 23rd, 2006, 4:18pm
Ah.  There is indeed a [link=http://base.google.com/base_image?q=hand7941761016343606377&size=6]picture[/link] hiding between Jock's [edit2] tags.  Interesting.  Could you explain exactly how that was made?
Title: Re: Fibonacci mod(m)
Post by Grimbal on Feb 23rd, 2006, 4:32pm
a picture? where?
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 24th, 2006, 8:51am

on 02/23/06 at 16:18:28, Eigenray wrote:
Ah.  There is indeed a [link=http://base.google.com/base_image?q=hand7941761016343606377&size=6]picture[/link] 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...


Title: Re: Fibonacci mod(m)
Post by SMQ on Feb 24th, 2006, 10:13am

on 02/23/06 at 16:32:14, Grimbal wrote:
a picture? where?

(tries View->Page Source) Aha! here (http://base.google.com/base_image?q=hand7941761016343606377&size=6)
8)


[edit]

http://base.google.com/base_image?q=hand7941761016343606377&size=6

copy and paste to the address bar seems to wrk consistently; see below

[/edit]


--SMQ
Title: Re: Fibonacci mod(m)
Post by Icarus on Feb 25th, 2006, 4:55pm
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?
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 25th, 2006, 6:22pm

on 02/25/06 at 16:55:43, 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?
Title: Re: Fibonacci mod(m)
Post by SMQ on Feb 25th, 2006, 8:49pm

on 02/25/06 at 16:55:43, 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
Title: Re: Fibonacci mod(m)
Post by Icarus on Feb 26th, 2006, 1:41pm
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).
Title: Re: Fibonacci mod(m)
Post by JocK on Feb 26th, 2006, 2:25pm

on 02/26/06 at 13:41:43, 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=6838743187121338456
Title: Re: Fibonacci mod(m)
Post by Barukh on Feb 28th, 2006, 4:40am
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.
Title: Re: Fibonacci mod(m)
Post by Michael_Dagg on Mar 6th, 2006, 1:05pm
Another proof of this fact can be found here http://www.mathpages.com/home/kmath078.htm


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board