Given-Fibonacci-series-F-1-F-2-1-and-F-n-2-F-n-1-F-n-for-n-gt-0-Find-the-remainder-F-2022-divides-by-5-

Question Number 199625 by cortano12 last updated on 06/Nov/23

Given Fibonacci series

F_{1} = F_{2} = 1 and F_{n + 2} = F_{n + 1} + F_{n}

for n > 0 . Find the remainder

F_{2022} divides by 5

Answered by witcher3 last updated on 06/Nov/23

F_{3} = 2, f_{4} = 3, f_{5} = 5, f_{6} = 8, f_{7} = 13, f_{8} = 21, f_{9} = 34

f_{10} = 55, f_{11} = 89, f_{12} = 144, f_{13} = 233,

X^{2} - X - 1 = 0

X = \frac{1 + \sqrt{5}}{2}, \frac{1 - \sqrt{5}}{2}

a {(\frac{1 + \sqrt{5}}{2})}^{n} + b {(\frac{1 - \sqrt{5}}{2})}^{n} = u_{n}

\frac{a + b}{2} + \frac{\sqrt{5}}{2} (a - b) = 1

a (\frac{6 + 2 \sqrt{5}}{4}) + b (\frac{6 - 2 \sqrt{5}}{4}) = 1

\frac{\sqrt{5}}{2} (a - b) + \frac{3}{2} (a + b) = 1

a + b = 0 \Rightarrow a = - b

a = \frac{1}{\sqrt{5}}

f_{n} = \frac{1}{\sqrt{5}} [{(\frac{\sqrt{5} + 1}{2})}^{n} - \frac{{(1 - \sqrt{5})}^{n}}{2^{n}}]

f_{n} = \frac{1}{2^{n}} \frac{1}{\sqrt{5}} (\underset{k = 0}{\sum^{n}} ((\begin{matrix} n \\ k \end{matrix}) ({(\sqrt{5})}^{k} - {(- \sqrt{5})}^{k})

2^{n} f_{n} = 2 \underset{k = 0}{\sum^{[\frac{n - 1}{2}]}} (\begin{matrix} n \\ 2 k + 1 \end{matrix}) (5^{k}) \equiv 2 n [5]

n = 4 k \Rightarrow 2^{n} \equiv 1 [5], 2^{n} f_{n} \equiv f_{n} [5]

n = 4 k + 1 \Rightarrow 2^{n} \equiv 2 [5], 2^{n} f_{n} \equiv {2 f}_{n} [5]

n = 4 k + 2 \Rightarrow 2^{n} f_{n} \equiv {4 f}_{n} [5]

n \equiv 4 k + 3 \Rightarrow 2^{n} f_{n} \equiv {3 f}_{n} [5]

n = 2022 \equiv 2 [4]

2^{2022} \equiv 4 [5] \Rightarrow {4 f}_{2022} \equiv 2.2022 [5]

\Leftrightarrow {4 f}_{2022} \equiv 4 [5] \Leftrightarrow f_{2002} \equiv 1 [5]

mor generaly

2^{n} f_{n} \equiv 2 n [5], 2 n = 5 g + r

n = 4 k + t \Rightarrow 2^{4 k + t} \equiv 2^{t} [5]

\Leftrightarrow 2^{n} f_{n} \equiv 2^{t} f_{n} \equiv 2 n [5] \equiv r [5]

2^{t} f_{n} \equiv r [5] \Rightarrow 2^{4 - t} . 2^{t} f_{n} \equiv 2^{4 - t} r [5]

\Leftrightarrow f_{n} = 2^{4 - t} r [5], Exempl

n = 13, t = 1, 2.13 = 26 \Rightarrow r = 1

f_{13} \equiv 2^{4 - 1} . 1 [5] \equiv 8 = 3 [5] . true

f_{13} = 233

Facebook Tweet Pin