# congruence and Fibonacci numbers remainder

$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...

-
my teacher asked exactly this one question.. – baaa12 Dec 5 '12 at 0:15
There are only so many pairs of residues mod $n$, and yet the sequence of pairs is infinite. – anon Dec 5 '12 at 0:21
Where to start? At the definition: $f_{n+1}=f_n+f_{n-1}$. – Berci Dec 5 '12 at 0:24
@Berci I already know the definition but from there... – baaa12 Dec 5 '12 at 0:33

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.

-
You need to say more than that to prove that it continues repeating. – Bill Dubuque Dec 5 '12 at 0:44

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.

-
We didnt learn those things I need to use congurence... – baaa12 Dec 5 '12 at 0:33
@baaa12 This does use congruences. What "things" are unknown, mod, matrices, pigeonholes? – Bill Dubuque Dec 5 '12 at 0:34
pigeonholes...??? – baaa12 Dec 5 '12 at 1:16
@baaa12 See the Wikipedia page on the pigeonhole (box) 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). – Bill Dubuque Dec 5 '12 at 1:19