Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.