Question Number 199625 by cortano12 last updated on 06/Nov/23
$$\mathrm{Given}\:\mathrm{Fibonacci}\:\mathrm{series}\: \\ $$$$\:\mathrm{F}_{\mathrm{1}} =\mathrm{F}_{\mathrm{2}} =\:\mathrm{1}\:\mathrm{and}\:\mathrm{F}_{\mathrm{n}+\mathrm{2}} =\:\mathrm{F}_{\mathrm{n}+\mathrm{1}} +\mathrm{F}_{\mathrm{n}} \\ $$$$\:\mathrm{for}\:\mathrm{n}>\mathrm{0}.\:\mathrm{Find}\:\mathrm{the}\:\mathrm{remainder}\: \\ $$$$\:\mathrm{F}_{\mathrm{2022}} \:\mathrm{divides}\:\mathrm{by}\:\mathrm{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=((1+(√5))/2),((1−(√5))/2) a(((1+(√5))/2))^n +b(((1−(√5))/2))^n =u_n ((a+b)/2)+((√5)/2)(a−b)=1 a(((6+2(√5))/4))+b(((6−2(√5))/4))=1 ((√5)/2)(a−b)+(3/2)(a+b)=1 a+b=0⇒a=−b a=(1/( (√5))) f_n =(1/( (√5)))[((((√5)+1)/2))^n −(((1−(√5))^n )/2^n )] f_n =(1/2^n )(1/( (√5)))(Σ_(k=0) ^n ( ((n),(k) )(((√5))^k −(−(√5))^k ) 2^n f_n =2Σ_(k=0) ^([((n−1)/2)]) ((n),((2k+1)) )(5^k )≡2n[5] n=4k⇒2^n ≡1[5],2^n f_n ≡f_n [5] n=4k+1⇒2^n ≡2[5],2^n f_n ≡2f_n [5] n=4k+2⇒2^n f_n ≡4f_n [5] n≡4k+3⇒2^n f_n ≡3f_n [5] n=2022≡2[4] 2^(2022) ≡4[5]⇒4f_(2022) ≡2.2022[5] ⇔4f_(2022) ≡4[5]⇔f_(2002) ≡1[5] mor generaly 2^n f_n ≡2n[5],2n=5g+r n=4k+t⇒2^(4k+t) ≡2^t [5] ⇔2^n f_n ≡2^t f_n ≡2n[5]≡r[5] 2^t f_n ≡r[5]⇒2^(4−t) .2^t f_n ≡2^(4−t) r[5] ⇔f_n =2^(4−t) r[5],Exempl n=13,t=1,2.13=26⇒r=1 f_(13) ≡2^(4−1) .1[5]≡8=3[5].true f_(13) =233](https://www.tinkutara.com/question/Q199627.png)
$$\mathrm{F}_{\mathrm{3}} =\mathrm{2},\mathrm{f}_{\mathrm{4}} =\mathrm{3},\mathrm{f}_{\mathrm{5}} =\mathrm{5},\mathrm{f}_{\mathrm{6}} =\mathrm{8},\mathrm{f}_{\mathrm{7}} =\mathrm{13},\mathrm{f}_{\mathrm{8}} =\mathrm{21},\mathrm{f}_{\mathrm{9}} =\mathrm{34} \\ $$$$\mathrm{f}_{\mathrm{10}} =\mathrm{55},\mathrm{f}_{\mathrm{11}} =\mathrm{89},\mathrm{f}_{\mathrm{12}} =\mathrm{144},\mathrm{f}_{\mathrm{13}} =\mathrm{233}, \\ $$$$\mathrm{X}^{\mathrm{2}} −\mathrm{X}−\mathrm{1}=\mathrm{0} \\ $$$$\mathrm{X}=\frac{\mathrm{1}+\sqrt{\mathrm{5}}}{\mathrm{2}},\frac{\mathrm{1}−\sqrt{\mathrm{5}}}{\mathrm{2}} \\ $$$$\mathrm{a}\left(\frac{\mathrm{1}+\sqrt{\mathrm{5}}}{\mathrm{2}}\right)^{\mathrm{n}} +\mathrm{b}\left(\frac{\mathrm{1}−\sqrt{\mathrm{5}}}{\mathrm{2}}\right)^{\mathrm{n}} =\mathrm{u}_{\mathrm{n}} \\ $$$$\frac{\mathrm{a}+\mathrm{b}}{\mathrm{2}}+\frac{\sqrt{\mathrm{5}}}{\mathrm{2}}\left(\mathrm{a}−\mathrm{b}\right)=\mathrm{1} \\ $$$$\mathrm{a}\left(\frac{\mathrm{6}+\mathrm{2}\sqrt{\mathrm{5}}}{\mathrm{4}}\right)+\mathrm{b}\left(\frac{\mathrm{6}−\mathrm{2}\sqrt{\mathrm{5}}}{\mathrm{4}}\right)=\mathrm{1} \\ $$$$\frac{\sqrt{\mathrm{5}}}{\mathrm{2}}\left(\mathrm{a}−\mathrm{b}\right)+\frac{\mathrm{3}}{\mathrm{2}}\left(\mathrm{a}+\mathrm{b}\right)=\mathrm{1} \\ $$$$\mathrm{a}+\mathrm{b}=\mathrm{0}\Rightarrow\mathrm{a}=−\mathrm{b} \\ $$$$\mathrm{a}=\frac{\mathrm{1}}{\:\sqrt{\mathrm{5}}} \\ $$$$\mathrm{f}_{\mathrm{n}} =\frac{\mathrm{1}}{\:\sqrt{\mathrm{5}}}\left[\left(\frac{\sqrt{\mathrm{5}}+\mathrm{1}}{\mathrm{2}}\right)^{\mathrm{n}} −\frac{\left(\mathrm{1}−\sqrt{\mathrm{5}}\right)^{\mathrm{n}} }{\mathrm{2}^{\mathrm{n}} }\right] \\ $$$$\mathrm{f}_{\mathrm{n}} =\frac{\mathrm{1}}{\mathrm{2}^{\mathrm{n}} }\frac{\mathrm{1}}{\:\sqrt{\mathrm{5}}}\left(\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\left(\begin{pmatrix}{\mathrm{n}}\\{\mathrm{k}}\end{pmatrix}\left(\left(\sqrt{\mathrm{5}}\right)^{\mathrm{k}} −\left(−\sqrt{\mathrm{5}}\right)^{\mathrm{k}} \right)\right.\right. \\ $$$$\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} =\mathrm{2}\underset{\mathrm{k}=\mathrm{0}} {\overset{\left[\frac{\mathrm{n}−\mathrm{1}}{\mathrm{2}}\right]} {\sum}}\begin{pmatrix}{\mathrm{n}}\\{\mathrm{2k}+\mathrm{1}}\end{pmatrix}\left(\mathrm{5}^{\mathrm{k}} \right)\equiv\mathrm{2n}\left[\mathrm{5}\right] \\ $$$$\mathrm{n}=\mathrm{4k}\Rightarrow\mathrm{2}^{\mathrm{n}} \equiv\mathrm{1}\left[\mathrm{5}\right],\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{f}_{\mathrm{n}} \left[\mathrm{5}\right] \\ $$$$\mathrm{n}=\mathrm{4k}+\mathrm{1}\Rightarrow\mathrm{2}^{\mathrm{n}} \equiv\mathrm{2}\left[\mathrm{5}\right],\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{2f}_{\mathrm{n}} \left[\mathrm{5}\right] \\ $$$$\mathrm{n}=\mathrm{4k}+\mathrm{2}\Rightarrow\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{4f}_{\mathrm{n}} \left[\mathrm{5}\right] \\ $$$$\mathrm{n}\equiv\mathrm{4k}+\mathrm{3}\Rightarrow\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{3f}_{\mathrm{n}} \left[\mathrm{5}\right] \\ $$$$\mathrm{n}=\mathrm{2022}\equiv\mathrm{2}\left[\mathrm{4}\right] \\ $$$$\mathrm{2}^{\mathrm{2022}} \equiv\mathrm{4}\left[\mathrm{5}\right]\Rightarrow\mathrm{4f}_{\mathrm{2022}} \equiv\mathrm{2}.\mathrm{2022}\left[\mathrm{5}\right] \\ $$$$\Leftrightarrow\mathrm{4f}_{\mathrm{2022}} \equiv\mathrm{4}\left[\mathrm{5}\right]\Leftrightarrow\mathrm{f}_{\mathrm{2002}} \equiv\mathrm{1}\left[\mathrm{5}\right] \\ $$$$\mathrm{mor}\:\mathrm{generaly} \\ $$$$\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{2n}\left[\mathrm{5}\right],\mathrm{2n}=\mathrm{5g}+\mathrm{r} \\ $$$$\mathrm{n}=\mathrm{4k}+\mathrm{t}\Rightarrow\mathrm{2}^{\mathrm{4k}+\mathrm{t}} \equiv\mathrm{2}^{\mathrm{t}} \left[\mathrm{5}\right] \\ $$$$\Leftrightarrow\mathrm{2}^{\mathrm{n}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{2}^{\mathrm{t}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{2n}\left[\mathrm{5}\right]\equiv\mathrm{r}\left[\mathrm{5}\right] \\ $$$$\mathrm{2}^{\mathrm{t}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{r}\left[\mathrm{5}\right]\Rightarrow\mathrm{2}^{\mathrm{4}−\mathrm{t}} .\mathrm{2}^{\mathrm{t}} \mathrm{f}_{\mathrm{n}} \equiv\mathrm{2}^{\mathrm{4}−\mathrm{t}} \mathrm{r}\left[\mathrm{5}\right] \\ $$$$\Leftrightarrow\mathrm{f}_{\mathrm{n}} =\mathrm{2}^{\mathrm{4}−\mathrm{t}} \mathrm{r}\left[\mathrm{5}\right],\mathrm{Exempl} \\ $$$$\mathrm{n}=\mathrm{13},\mathrm{t}=\mathrm{1},\mathrm{2}.\mathrm{13}=\mathrm{26}\Rightarrow\mathrm{r}=\mathrm{1} \\ $$$$\mathrm{f}_{\mathrm{13}} \equiv\mathrm{2}^{\mathrm{4}−\mathrm{1}} .\mathrm{1}\left[\mathrm{5}\right]\equiv\mathrm{8}=\mathrm{3}\left[\mathrm{5}\right].\mathrm{true} \\ $$$$\mathrm{f}_{\mathrm{13}} =\mathrm{233} \\ $$