Question

The Fibonacci sequence is defined by F_1 = F_2 = 1 and F_{n + 2} = F_{n + 1} + F_n. Find the remainder when F_{1999} is divided by 5.

Answer 1

damn i was waiting for an answer
a (somewhat) will known result is that every fifth fibonnaci is divisible by 5, but 1999 is one off so not sure what to do in that case

Answer 2

*well known

Answer 3

umm...thanks? (though your not even here) XD

Answer 4

*you're

Answer 5

maybe there is a pattern for remainders

Answer 6

maybe :)

Answer 7

@satellite73 there is indeed; lookup the Pisano periods. my calculus II teacher told me he discovered the same idea back in undergraduate number theory but couldn't prove that the Fibonacci sequence was periodic mod n for any positive integer n

Answer 8

anyways, we know it's not \(0\) because:$$\gcd(F_n,F_m)=F_{\gcd(n,m)}$$since \(F_5=5\) we have:$$\gcd(F_{1999},F_5)=F_{\gcd(1999,5)}$$now, since \(1999\) is prime, we have \(\gcd(1999,5)=1\) hence \(\gcd(F_{1999},F_5)=F_1=1\) i.e. \(5\) does not divide \(F_{1999}\)

Answer 9

1,1,2,3,5=0,8=3,13=3,21=1,34=4,55=0,

Answer 10

hmm not sure what the pattern is

Answer 11

http://en.wikipedia.org/wiki/Pisano_period#Tables
hence the period \(\mod 5\) is \(20\) yielding the cycle \(01123 03314 04432 02241\)

Answer 12

01123 03314 04432 02241

Answer 13

thanks wiki!
learn something new every day!

Answer 14

lol :)

Answer 15

wait...

Answer 16

oh no

Answer 17

and thanks @oldrin.bataku for the "pisano period" never saw that before

Answer 18

but shouldn't it be 1 ?

Answer 19

sorry, I MEANT to do \(1999\equiv-1\pmod{20}\) hence we look at the last number in the cycle

Answer 20

i.e. \(F_{1999}\equiv1\pmod5\) yes

Answer 21

$$01123 03314 04432 0224\color{red}1$$

Answer 22

that makes sense. Thanks again oldrin :)

Answer 23

01123 03314 04432 02241
has 20 numbers
and 20 goes in to 2000 evenly, count back one and get 1

Answer 24

good thing you don't have to prove this i guess

Answer 25

np @orple8 this one I kept forgetting how to solve... I've done a proof before demonstrating periodicity for said teacher but I'm not sure how to prove \(\pi(5)=20\)

Answer 26

my guess is induction since almost anything with fibonacci means induction

Answer 27

I did it using a little bit of group theory I think... it was a semester or so ago

Answer 28

I checked it using by mathematica, and it is 1

Answer 29

or just: http://www.wolframalpha.com/input/?i=F_1999+mod+5

Answer 30

true :)

Answer 31

\[F(n)= \frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt5}\]

Answer 32

yes @cinar that is Binet's formula. you can derive it trivially trying to solve the IVP \(F_n=F_{n-1}+F_{n-2},F_1=F_2=1\) with the ansatz \(F_n=r^n\)

Answer 33

for example:$$r^n=r^{n-1}+r^{n-2}\\r^n-r^{n-1}-r^{n-2}=0\\r^{n-2}(r^2-r-1)=0$$hence we see that \(r=0\) yields the trivial solution \(F_n=0\) but that the solutions to \(r^2-r-1=0\) give a significantly more interesting one...$$r^2-r-1=0\\r=\frac{1\pm\sqrt{1^2-4(-1)}}2=\frac{1\pm\sqrt5}2$$hence we get \(r=\varphi,1/\varphi+1\) i.e. the golden ratio and its conjugate

Answer 34

oops that should be \(r=\varphi,1-\varphi\) thus we get two 'fundamental' solutions \(F_n=\varphi^n,F_n=(1-\varphi)^n\) as candidates and (just like linear differential equations) we find that any linear combination of these two satisfies our equations similarly i.e. \(F_n=A\varphi^n+B(1-\varphi)^n\). consider our initial conditions, \(F_1=F_2=1\):$$F_1=1\\A\varphi+B(1-\varphi)=1\\A\varphi-B\varphi+B=1\\(A-B)\varphi=1-B\\F_2=1\\~\\A\varphi^2+B(1-\varphi)^2=1\\A\varphi^2+B(1-2\varphi+\varphi^2)=1\\A\varphi^2+B\varphi^2-2B\varphi+B=1\\(A+B)\varphi^2-2B\varphi=1-B$$using the fact \(\varphi^2=1+\varphi\):$$(A+B)(1+\varphi)-2B\varphi=1-B\\A+B+(A-B)\varphi=1-B$$equating both equations of \(1-B\):$$A+B+(A-B)\varphi=(A-B)\varphi\\A+B=0\\B=-A$$hence:$$A-A+(A+A)\varphi=1+A\\2A\varphi=1+A\\2A\varphi-A=1\\A(2\varphi-1)=1\\A=\frac1{2\varphi-1}=\frac1{\sqrt5}$$ hence \(B=-\dfrac1{\sqrt5}\)

Answer 35

hence:$$F_n=\frac1{\sqrt5}(\varphi^n-(1-\varphi)^n)$$