Results 1 to 2 of 2

Math Help - Modulo of fibonacci sequence

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    Modulo of fibonacci sequence

    Hi everybody,

    We can easy observe that result of Fibonacci sequnce according to modulo of a number M is pierodic. However on internet there are proofs like the following:

    Perhaps the first thing one notices when the Fibonacci sequence is reduced mod m is that it is periodic. For example, F(mod 4) = 0 1 1 2 3 1 0 1 1 2 3 ... F(mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 ...

    Any (generalized) Fibonacci sequence modulo m must repeat. After all, there are only m^2 possible pairs of residues and any pair will completely determine a sequence both forward and backward. If we ignore the pair 0,0 which gives us the trivial sequence, then we know that the period of any Fibonacci sequence mod m has a maximum length of m^2-1.
    It will always happen that the first pair to repeat will be the pair we started with. Suppose that this were not so. Then we might have the sequence a,b,...,x,y,...,x,y,... where the pair a,b is not contained in the block x,y,...,x,y. However, we know that this block repeats backward as well as forward, and so the pair a,b cannot be in the sequence. This gives us our contradiction.
    Is this claim capable for proof ???

    Is it so simple to prove that modulo of fibonacci sequence is periodic???

    Thank you all for your time
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Look Theorem 6 here.



    Fernando Revilla
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 6th 2010, 07:34 AM
  2. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 28th 2010, 03:54 AM
  3. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  4. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 11:47 PM
  5. Fibonacci's sequence
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: June 11th 2006, 08:04 AM

Search Tags


/mathhelpforum @mathhelpforum