Question and Answers Forum

All Questions      Topic List

Coordinate Geometry Questions

Previous in All Question      Next in All Question      

Previous in Coordinate Geometry      Next in Coordinate Geometry      

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

$$\mathrm{Given}\mathrm{Fibonacci}\mathrm{series}$$$${\mathrm{F}}_1={\mathrm{F}}_2=1\mathrm{and}{\mathrm{F}}_{\mathrm{n}+2}={\mathrm{F}}_{\mathrm{n}+1}+{\mathrm{F}}_{\mathrm{n}}$$$$\mathrm{for}\mathrm{n}>0.\mathrm{Find}\mathrm{the}\mathrm{remainder}$$$${\mathrm{F}}_{2022}\mathrm{divides}\mathrm{by}5$$

Answered by witcher3 last updated on 06/Nov/23

$${\mathrm{F}}_3=2,{\mathrm{f}}_4=3,{\mathrm{f}}_5=5,{\mathrm{f}}_6=8,{\mathrm{f}}_7=13,{\mathrm{f}}_8=21,{\mathrm{f}}_9=34$$$${\mathrm{f}}_{10}=55,{\mathrm{f}}_{11}=89,{\mathrm{f}}_{12}=144,{\mathrm{f}}_{13}=233,$$$${\mathrm{X}}^2-\mathrm{X}-1=0$$$$\mathrm{X}=\frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}$$$$\mathrm{a}{\left(\frac{1+\sqrt{5}}{2}\right)}^{\mathrm{n}}+\mathrm{b}{\left(\frac{1-\sqrt{5}}{2}\right)}^{\mathrm{n}}={\mathrm{u}}_{\mathrm{n}}$$$$\frac{\mathrm{a}+\mathrm{b}}{2}+\frac{\sqrt{5}}{2}(\mathrm{a}-\mathrm{b})=1$$$$\mathrm{a}\left(\frac{6+2\sqrt{5}}{4}\right)+\mathrm{b}\left(\frac{6-2\sqrt{5}}{4}\right)=1$$$$\frac{\sqrt{5}}{2}(\mathrm{a}-\mathrm{b})+\frac{3}{2}(\mathrm{a}+\mathrm{b})=1$$$$\mathrm{a}+\mathrm{b}=0\Rightarrow \mathrm{a}=-\mathrm{b}$$$$\mathrm{a}=\frac{1}{\sqrt{5}}$$$${\mathrm{f}}_{\mathrm{n}}=\frac{1}{\sqrt{5}}[{\left(\frac{\sqrt{5}+1}{2}\right)}^{\mathrm{n}}-\frac{{(1-\sqrt{5})}^{\mathrm{n}}}{2^{\mathrm{n}}}]$$$${\mathrm{f}}_{\mathrm{n}}=\frac{1}{2^{\mathrm{n}}}\frac{1}{\sqrt{5}}(\underset{\mathrm{k}=0}{\sum ^{\mathrm{n}}}(\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)({\left(\sqrt{5}\right)}^{\mathrm{k}}-{(-\sqrt{5})}^{\mathrm{k}})$$$$2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}=2\underset{\mathrm{k}=0}{\sum ^{\left[\frac{\mathrm{n}-1}{2}\right]}}\left(\begin{array}{c}\mathrm{n}\\ 2\mathrm{k}+1\end{array}\right)\left(5^{\mathrm{k}}\right)\equiv 2\mathrm{n}\left[5\right]$$$$\mathrm{n}=4\mathrm{k}\Rightarrow 2^{\mathrm{n}}\equiv 1\left[5\right],2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv {\mathrm{f}}_{\mathrm{n}}\left[5\right]$$$$\mathrm{n}=4\mathrm{k}+1\Rightarrow 2^{\mathrm{n}}\equiv 2\left[5\right],2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv {2\mathrm{f}}_{\mathrm{n}}\left[5\right]$$$$\mathrm{n}=4\mathrm{k}+2\Rightarrow 2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv {4\mathrm{f}}_{\mathrm{n}}\left[5\right]$$$$\mathrm{n}\equiv 4\mathrm{k}+3\Rightarrow 2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv {3\mathrm{f}}_{\mathrm{n}}\left[5\right]$$$$\mathrm{n}=2022\equiv 2\left[4\right]$$$$2^{2022}\equiv 4\left[5\right]\Rightarrow {4\mathrm{f}}_{2022}\equiv 2.2022\left[5\right]$$$$\iff {4\mathrm{f}}_{2022}\equiv 4\left[5\right]\iff {\mathrm{f}}_{2002}\equiv 1\left[5\right]$$$$\mathrm{mor}\mathrm{generaly}$$$$2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv 2\mathrm{n}\left[5\right],2\mathrm{n}=5\mathrm{g}+\mathrm{r}$$$$\mathrm{n}=4\mathrm{k}+\mathrm{t}\Rightarrow 2^{4\mathrm{k}+\mathrm{t}}\equiv 2^{\mathrm{t}}\left[5\right]$$$$\iff 2^{\mathrm{n}}{\mathrm{f}}_{\mathrm{n}}\equiv 2^{\mathrm{t}}{\mathrm{f}}_{\mathrm{n}}\equiv 2\mathrm{n}\left[5\right]\equiv \mathrm{r}\left[5\right]$$$$2^{\mathrm{t}}{\mathrm{f}}_{\mathrm{n}}\equiv \mathrm{r}\left[5\right]\Rightarrow 2^{4-\mathrm{t}}.2^{\mathrm{t}}{\mathrm{f}}_{\mathrm{n}}\equiv 2^{4-\mathrm{t}}\mathrm{r}\left[5\right]$$$$\iff {\mathrm{f}}_{\mathrm{n}}=2^{4-\mathrm{t}}\mathrm{r}\left[5\right],\mathrm{Exempl}$$$$\mathrm{n}=13,\mathrm{t}=1,2.13=26\Rightarrow \mathrm{r}=1$$$${\mathrm{f}}_{13}\equiv 2^{4-1}.1\left[5\right]\equiv 8=3\left[5\right].\mathrm{true}$$$${\mathrm{f}}_{13}=233$$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com