2
$\begingroup$

A mod $n$ Fibonacci sequence is simply defined as the Fibonacci sequence, except all terms are in mod $n$.

Now to determine periodicity, the worked solutions computed the first 20 or so terms and then observed that it was periodic with period 16.

My question is: Just by testing terms like that, how do we REALLY know for sure that the period is 16?

How do we know that say when we test the first 20 terms, the 17th, 18th, 19th etc match the 2nd, 3rd, 4th etc term respectively, but then everything else goes wrong afterwards?

$\endgroup$
  • 3
    $\begingroup$ You have the defining recurrence, which is identical modulo $n$. Then you only need to observe the next pair $0,1$ of consecutive modular Fibonacci numbers to have the period. $\endgroup$ – Daniel Fischer Nov 17 '14 at 11:49
4
$\begingroup$

If $F_{16} \equiv F_0 \equiv 0 \text{ modulo }n$ and $F_{17} \equiv F_1 \equiv 1 \text{ modulo }n$ then you can use induction to show $F_{16+k} \equiv F_k \text{ modulo }n$ for all non-negative integer $k$.

This does not guarantee that the period is $16$, but it does ensure the period divides $16$: for example with $n=3$ you have $F_{16+k} \equiv F_k \text{ modulo }3$ but the period is $8$. So to ensure the period is exactly $16$ you also need to check it is not shorter, i.e. that it is not $1,2,4,8$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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