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$.

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$.

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

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

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

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).

(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$.

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

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.

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.

(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

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?