The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. (a) Prove that $f_{2010} $ is divisible by $10$. (b) Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4.
Problem
Source:
Tags: algorithm, algebra, system of equations, number theory unsolved, number theory
05.03.2011 22:30
lemma 1: $n\mid m$ then $f_n\mid f_m$ lemma 2:if $(m,n)=d$ then $(f_m,f_n)=f_d$ $(a)$:by lemma : $5\mid 2010 \Longrightarrow f_5\mid f_{2010}$ $(f_5=5)$ $6\mid 2010 \Longrightarrow f_6\mid f_{2010}$ $(f_6=8)$ $\Longrightarrow 40\mid f_{2010}$ $(b)$:by lemma 2 $(f_6,f_{1005})=f_3 \Longrightarrow (8,f_{1005})=2$ so $f_{1005}$ is not divisible by $4$.
05.03.2011 22:43
ridgers wrote: The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. (a) Prove that $f_{2010} $ is divisible by $10$. (b) Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4. Honestly, I do not consider this a very suitable problem for an Olympiad Contest. But that's maybe just my taste ... (a) The period of $f_{n}$ $\mod {10}$ is of length 60 and equals 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, **0**, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1 Therefore $2010 = 30 \mod {60}$ completes this part. (b) It is easily checked that the period of $f_{n}$ $\mod {4}$ has length 6. Thus $f_{1005}$ is not divisible by $4$.
05.03.2011 22:44
Hey there, First of all...you need to know what form has f_{n} and we can do that by using the caracteristic equation of the 2nd order linear recurrent. we will have : $ f_{n+2} = t^2$ ;$ f_{n+1}=t$;$ f_{n}=1$; from this results => $ t^2 - t - 1=0$ ( caracteristic equation ) Delta is 5 so we will have $t_{1} = (1+sqrt(5))/2$ and $t_{2}=(1-sqrt(5))/2$ From theory , because t_{1} is different from t_{2}, the form of f_{n} is : $f_{n}= A * ( (1+sqrt(5))/2 ) ^n + B * ( (1-sqrt(5))/2 ) ^n $, where A = f_{1} and B=f_{2} now we will make a system of equations using n=1 and n=2 $f_{1}= A* ((1+sqrt(5))/2) + B*((1-sqrt(5))/2)$ $f_{2}=A*((1+sqrt(5))/2)^2 + B*((1-sqrt(5))/2)^2$ At final we will have : $ f_{n}= sqrt(5)/5 *[((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n]$ Just put n=2010 and you will see that is divisible for point b) the answer is No
05.03.2011 23:11
Hey again, Another easier solution is a theoretical one: a) Lemma 1 : f_{n} is a even number only if n divides 3 Lemma 2 :$ 5 | f_{n}$ only if $ 5 | n$ By using Lemma 1 and 2, $10 | f_{2010}$ b) Lemma 3: $4|f_{n}$ only if $6|n$ so the answer is No
06.03.2011 06:53
ridgers wrote: The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. (a) Prove that $f_{2010} $ is divisible by $10$. (b) Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4. For (a) well known that $gcd(f_m,f_n)=f_{gcd(m,n)}$ Then $f_3=2|f_{2010}$ and $f_{10}=55|f_{2010}$ and because $gcd(2,55)=1,110|2010$ For (b) consider $\mod 4$ on the sequence $f_n$,we get $1,1,2,-1,1,0,1,1,2,-1,1,0,....,1,1,2,-1,1,0,....$ the sequence periodic with period $6$ So $f_{1005}\equiv f_3\equiv 2\mod 4$ Edit:Too stupid mistake to consider
06.03.2011 14:53
mathmdmb wrote: ridgers wrote: The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. (a) Prove that $f_{2010} $ is divisible by $10$. (b) Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4. For (a) well known that $gcd(f_m,f_n)=f_{gcd(m,n)}$ Then $f_3=2|f_{2010}$ and $f_{10}=55|f_{2010}$ and because $gcd(2,55)=1,110|2010$ For (b) consider $\mod 4$ on the sequence $f_n$,we get $1,1,2,-1,1,0,1,1,2,-1,1,0,....,1,1,2,-1,1,0,....$ the sequence periodic with period $6$ So $f_{1005}\equiv f_6\equiv 0\mod 4$ Sorry, there is a sort of mistake in your reasoning ... Indeed, $f_{1005}\equiv f_{**3**}\equiv 2\mod 4$ leads to the answer "NO" for question (b).
09.05.2012 18:14
(a) By the division algorithm, we have $\gcd (f_n, f_m)=f_{\gcd(m, n)}$; then $\gcd(f_{2010}, f_5)=f_5=5$, and $f_n$ is even iff $3|n$ (it is enough to write down the recurrence modulo $2$); it follows that $5 \cdot 2 |f_{2010}$. (b) We have, by the previous fact, that $\gcd(f_{1005}, 8)=\gcd(f_{1005}, f_6)=f_3=2$, so $f_{1005}$ is divisible by $2$ but not by $4$.
10.05.2012 08:54
well, it is a well known fact that m divides the mn- th term of fibboanci sequence.so the 1st part is quite trivial for the 2nd part , the answer is NO. it is easy . if u assume the contrary , u will readily arrive at a contradiction. seems to be very very easy for a national olympiad
21.06.2015 19:35
auj wrote: Honestly, I do not consider this a very suitable problem for an Olympiad Contest. But that's maybe just my taste ... (a) The period of $f_{n}$ $\mod {10}$ is of length 60 and equals 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, **0**, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1 Therefore $2010 = 30 \mod {60}$ completes this part. 5|f(5n) and 2|f(3n) so 10|f(15n) for all n.
21.05.2020 05:16
ridgers wrote: The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. (a) Prove that $f_{2010} $ is divisible by $10$. (b) Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4. Pisano period.
25.08.2023 00:56
(b) The pattern in mod 4, is: 1,1,2,3,1,0,1,1 this repeats in cycles of 6, so f_1005 is not divisible by 4
28.01.2024 17:29
mousavi wrote: lemma 1: $n\mid m$ then $f_n\mid f_m$ lemma 2:if $(m,n)=d$ then $(f_m,f_n)=f_d$ $(a)$:by lemma : $5\mid 2010 \Longrightarrow f_5\mid f_{2010}$ $(f_5=5)$ $6\mid 2010 \Longrightarrow f_6\mid f_{2010}$ $(f_6=8)$ $\Longrightarrow 40\mid f_{2010}$ $(b)$:by lemma 2 $(f_6,f_{1005})=f_3 \Longrightarrow (8,f_{1005})=2$ so $f_{1005}$ is not divisible by $4$. Proof of the lemmas?