0

Define Fibonacci Sequence $\{F_{n}\}$ such $$F_{0}=0,F_{1}=1,F_{n+2}=F_{n+1}+F_{n}$$ Find the $$F_{0}+F_{1}+F_{2}+\cdots+F_{2016}\equiv? \pmod {2017}$$

since $2017$ is prime number and $F_{p}\equiv\left(\frac{p}{5}\right) \pmod p$

math110
  • 93,304

3 Answers3

2

By Binet's explicit formula$^{(*)}$, if $p>5$ is a prime such that $5$ is a quadratic non-residue $\!\!\pmod{p}$ we have $F_{p-1}\equiv 1\pmod{p}$ and $F_p\equiv -1\pmod{p}$, hence $F_{p+1}\equiv 0\pmod{p}$. Since $$ F_0+F_1+\ldots+F_{p-1} = F_{p+1}-1$$ is straightforward to prove by induction, $$ F_0+F_1+\ldots+F_{2016}\equiv\color{red}{-1}\pmod{2017}$$ readily follows. Do I need to show $(*)$, too?

Jack D'Aurizio
  • 353,855
  • @N.S. no, since by quadratic reciprocity $$\left(\frac{5}{2017}\right)=\left(\frac{2017}{5}\right)=\left(\frac{2}{5}\right)=-1.$$ – Jack D'Aurizio Mar 02 '17 at 23:05
1

Hint Prove by induction that $$F_0+F_1+..+F_{n}=F_{n+2}-1 $$

N. S.
  • 132,525
  • so How to find $F_{2018}\equiv 0 \pmod {2017}?$ – math110 Mar 02 '17 at 14:02
  • @communnites Since $5$ is NOT a quadratic residue modulo $2017$, this is trickier. This means that $x^2=5$ doesn't have a root in $Z_{2017}$. Pick an algebraic extension $\mathbb F_{p^2}$ where $x^2=5$ has a root, then $x^2-x-1$ has two roots $\alpha, \beta$ in this extension. Now, if you consider the norm $N : \mathbb F_{p^2} \to \mathbb F_{p^2}$ of this extension, this norm gives a surjective group homomorphism $$N : (\mathbb F_{p^2}^, \cdot ) \to \mathbb (Z^_{p}, \cdot)$$ and the two roots are in the subgroup $$N^{-1} ( \pm 1)$$ By the first isomorphism theorem for groups – N. S. Mar 02 '17 at 23:08
  • this group has $2(p+1)$ elements. The elements in $Ker(N)$, are $p+1$ roots of $x^{p+1}=1$ and hence, the ones outside $Ker(N)$ satisfy $x^{p+1}=-1$. This shows that $$\alpha^{p+1}=\beta^{p+1}=-1$$ From here you can get easily the claim. I don't know any faster way. – N. S. Mar 02 '17 at 23:13
0

The sequence $F_0,F_1,F_2,\ldots$ can be written as a sum of two geometric sequences (see the closed form expression on wikipedia). You can then use the sum-formula for geometric series, and at the end you find that the answer is $-1$ mod 2017.

Mark
  • 1,247
  • Frankly, it would be a lot easier to write down some initial terms, guess the general term and prove it by induction, without ever mentioning the Binet formula or $1+\sqrt5\over2$. – Ivan Neretin Mar 02 '17 at 13:54
  • 1
    It turns out that $F_0 + \cdots + F_{p-1}$ mod $p$ equals: 2 mod $p$ (if $p=5$), $0$ mod $p$ (if $p$ is 1 or 4 mod 5), and $-1$ mod $p$ (if $p$ is 2 or 3 mod 5). – Mark Mar 02 '17 at 14:03