17
$\begingroup$

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this:

Fibonacci sequence:

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946\cdots$

Remainder when divided by $3$ sequence:

$1, 1, 2, 0, 2, 2, 01, 00, 01, 01, 02, 000, 002, 002, 001, 000, 0001, 0001, 0002, 0000, 00002\cdots$

I made each one the same number of digits to align them to avoid confusion. Is it true that it happens every eight numbers? If so, how and why does this happen?

$\endgroup$
31
$\begingroup$

A sequence like the Fibonacci sequence is completely determined by any of its segments of length $2$. Modulo any number $N$ (not just $3$) there are only finitely many possible segments of length $2$, in fact there are $N^2$ of them, so the sequence of remainders will eventually repeat itself and become periodic.

E.g.

  • modulo $5$ : $0$, $1$, $1$, $2$, $3$, $0$, $3$, $3$, $1$, $4$, $0$, $4$, $4$, $3$, $2$, $0$, $2$, $2$, $4$, $1$, $0$, $1$, ... (got back to the $0$, $1$ segment);

  • modulo $7$ : $0$, $1$, $1$, $2$, $3$, $5$, $1$, $6$, $0$, $6$, $6$, $5$, $4$, $2$, $6$, $1$, $0$, $1$, ... (got back to the $0$, $1$ segment again).

It is an interesting "exercise" to compute the length of the period of the sequence modulo a prime $p$ without actually computing the whole sequence.

$\endgroup$
  • $\begingroup$ You divided each one by five and seven in the sequence and found two more patterns! I get why they say "modulo" (any number) for something now. $\endgroup$ – ReliableMathBoy Jan 12 '15 at 14:54
  • $\begingroup$ It may be worth looking at what happens when you represent residues larger than N/2 by negative numbers between -N/2 and 0, and why it happens. For example, N = 3 gives [0,1,1,-1,0,-1,-1,1]. $\endgroup$ – James Wood Jan 12 '15 at 16:07
  • $\begingroup$ So... this would apply equally well to the Lucas numbers, right? $\endgroup$ – Kevin Jan 12 '15 at 23:16
  • $\begingroup$ Is there any way to find the period of the recurrence modulo n? $\endgroup$ – rah4927 Jan 13 '15 at 9:54
  • $\begingroup$ @Kevin: of course. It applies verbatim to all sequences $\{a_n\}$ such that $a_{n+k}=\sum_{i=0}^{k-1}A_ia_{n+i}$ with $A_i$ in $\Bbb Z$. $\endgroup$ – Andrea Mori Jan 13 '15 at 12:15
12
$\begingroup$

Since $f(n)=f(n-1)+f(n-2)$ the remainder when dividing by three of $f_n$ can be obtained by knowing the remainder of the other two numbers.

You just proved that the sequence starts $1,1,2,0,2,2,1,0,1,1$ After this we have to do exactly the same deduction we made at the beginning. Hence they do cycle.

$\endgroup$
12
$\begingroup$

They have to repeat. The two-term recursion $$F_n=F_{n-1}+F_{n-2}$$ yields the same recursion modulo $3$ for your modified sequence: $$f_n=f_{n-1}+f_{n-2}\mod 3$$ Each of the values can only take on $3$ distinct values, so there are at most $9$ different combinations of $f_{n-1}$ and $f_{n-2}$. It has to repeat after at most $9$ steps for any two-term recursion (not just the above), but for some, it may even repeat before that.

You can draw yourself a $3\times 3$ table and trace the path the sequence of ($f_{n-1}$,$f_{n-2}$) takes. It goes like (1,1), (1,2), (2,0), (0,2), (2,2), (2,1), (1,0), (0,1)...

You see that $(0,0)$ is not visited.

$\endgroup$
  • 2
    $\begingroup$ If (0,0) were visited, wouldn't that mean it would always be 0? Seems that segment must never be visited (assuming you don't start a similar sequence with two multiples of 3). $\endgroup$ – Joe Jan 12 '15 at 18:52
  • $\begingroup$ True. It depends on which subsequence you start. For this recursion, there are two chains: 1,1,2,0,2,2,1,0 and 0,0,0,0,0,0.... If you take other possible two-term recursions, it splits into different chains. Try $f_n=2(f_{n-1}+f_{n-2})\mod 3$. $\endgroup$ – orion Jan 12 '15 at 21:47
3
$\begingroup$

The method with the characteristic equation works also modulo $3$. Consider $$ x^2-x-1 $$ in the three element field $\mathbb{F}_3$. This polynomial has no roots, because the quadratic formula requires $\sqrt{5}=\sqrt{-1}$; if we add an element $i$ such that $i^2=-1$, the field extension in which the polynomial splits is thus $\mathbb{F}_3[i]$. The roots of the polynomial are then $$ \frac{1+i}{2}=-1-i,\qquad \frac{1-i}{2}=-1+i $$ and the general solution for the recurrence equation is $$ \alpha(-1-i)^n+\beta(-1+i)^n $$ where $\alpha,\beta\in\mathbb{F}_3$. Setting $F_0=0$ and $F_1=1$ gives $$ \alpha=-i,\qquad \beta=i $$ and so the terms of the Fibonacci sequence modulo $3$ are $$ i(-1+i)^n-i(-1-i)^n $$ In a field with $9$ elements such as $\mathbb{F}_3$ we have $z^8=1$ for all elements $z\ne0$, so the sequence will repeat with period $8$. Not less, because the other possible period would be $4$, which it isn't.

More generally, if the polynomial splits in $\mathbb{F}_p$ (for $p$ a prime different from $2$ and $5$), the period will be $p-1$; if it doesn't split, the period is $p^2-1$.

The case $p=2$ can be treated adding an element $j$ such that $j^2+j+1=0$ (the period is $3=2^2-1$). In the case of $p=5$ the characteristic equation has a repeated root $3$, so the general solution is of the form $$ \alpha\cdot 3^n+\beta\cdot n3^n $$ and the general term of the Fibonacci sequence modulo $5$ is $2n3^n$: $$ 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,\dotsc $$ that has period $20$. Indeed, in order to have $2(n+k)3^{n+k}=2n3^n$ for all $n$ we need $(n+k)3^k=n$ for all $n$. For $n=0$ this gives $k3^k=0$, so $k$ is divisible by $5$; for $n=1$ this gives $(1+k)3^k=1$. Setting $k=5h$ and recalling that $3^5\equiv 3\pmod{5}$, this becomes $3^h=1$ and the least positive solution for this is $h=4$.

$\endgroup$
2
$\begingroup$

Consider the pairs $(R_k,R_{k+1})$ with $R_k$ is the remainder of $F_k$ when dividing by $3$. Since there are infinitely many such pairs, by Pingeonhole principle there exists $k,l$ such that $(R_k,R_{k+1})=(R_l,R_{l+1})$. Thus $R_{k-1}=R_{l-1}$ and so on. So the remainders are periodic.

The same property is true for all sequence with linear recurrence (with the same method).

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