Results 1 to 2 of 2

Thread: Modulo of fibonacci sequence

  1. #1
    May 2009

    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
    Nov 2010
    Madrid, Spain
    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: Apr 6th 2010, 08:34 AM
  2. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 28th 2010, 04:54 AM
  3. Replies: 2
    Last Post: Mar 1st 2010, 12:57 PM
  4. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 15th 2009, 12:47 AM
  5. Fibonacci's sequence
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: Jun 11th 2006, 09:04 AM

Search Tags

/mathhelpforum @mathhelpforum