1
$\begingroup$

$M>0$ is an integer.

For every $n>-0$ the remainder for the n Fibonacci number divided by m is: $r_n = f_n mod n$.

I need to prove that in :

$((r_n,r_n+1)) = (r_0,r_1),(r_1,r_2),(r_2,r_3)...$ must be repeats of pairs

Will appreciate some guidance because I don't know where to start...

  • 0
    @Berci I already know the definition but from there...2012-12-05

2 Answers 2

1

As anon noted, there are only finitely many (exactly $M^2$) pairs, so in the infinite sequence there must be a repetition, say $(r_n,r_{n+1})=(r_k,r_{k+1})$, and $n>k$. Then, you should conlcude that $n-k$ is a period of this whole sequence.

  • 0
    You need to say more than that to prove that it *continues* repeating.2012-12-05
0

Hint $\rm\ (f_{n+1},f_{n+2}) = (f_n,f_{n+1}) A\:$ for an invertible matrix $\rm\:A,\:$ so $\rm\:(f_{n+k},f_{n+k+1}) = (f_n,f_{n+1}) A^k,\:$ and, by the pigeonhole/box principle, $\rm\:A^k\:$ has finite order mod $\rm\:n,\:$ yielding the sought cyclicity.

Alternatively $\rm\:A\:$ is an invertible map on a finite set $\rm\,\Bbb Z_n^2,\:$ i.e. a permutation, thus it has finite order. See this answer for further discussion of this viewpoint, where it is used to tackle the following problem: a sequence $\rm\:f(n)\:$ satisfies the relation $\rm\:f(n+2) = f(n+1)^2 - f(n),\,$ $\rm\,f(1) = 39,\ f(2) = 45.\:$ Prove that $1986$ divides infinitely many terms of the sequence.

  • 1
    @baaa12 See the Wi$k$ipedi$a$ page on the [pigeonhole ($b$ox) principle.](http://en.wi$k$ipedia.org/wiki/Pigeonhole_principle) I recommend that you say something in the question about your background, since that may help you receive answers at the appropriate level (which is impossible to infer from the question as it exists).2012-12-05