Given are two distinct sequences of positive integers $(a_n)$ and $(b_n)$, such that their first two members are coprime and smaller than $1000$, and each of the next members is the sum of the previous two. 8-9 grade Prove that if $a_n$ is divisible by $b_n$, then $n<50$ 10-11 grade Prove that if $a_n^{100}$ is divisible by $b_n$ then $n<5000$
Problem
Source: 239 MO (8-9).2/(10-11).3
Tags: number theory
23.10.2021 15:44
let $a_1=a, a_2=b, b_1=c, b_2=d$, by a straightforward induction we have: $$a_{n+2}=bF_{n+1}+aF_{n} , b_{n+2}=dF_{n+1}+cF_{n}$$where $F_n$ is the n-th Fibonacci number. note that $gcd(F_{n+1},F_{n})=1$. Now: $$ gcd(b_{n+2},F_{n+1} ^{100}) = gcd(dF_{n+1}+cF_{n},F_{n+1}^{100}) \mid gcd((dF_{n+1})^{101}+(cF_{n})^{101},F_{n+1}^{100})=gcd((cF_{n})^{101},F_{n+1}^{100})=gcd(c^{101},F_{n+1}^{100}) \mid c^{101}$$Now if the divisibility occurs for $n+2$, we conclude that $dF_{n+1}+cF_{n} \mid (bF_{n+1}+aF_{n})^{100}$ so $b_{n+2} \mid F_{n+1}^{100} (bc-ad)^{100}$ hence $b_{n+2} \mid c^{101} (bc-ad)^{100}$. finally by the assertion that $a,b,c,d\leq 1000$ : $$(\frac{(1+\sqrt{5})}{2})^{n-1}<F_{n+2}\leq b_{n+2} \leq 10^{903}$$which gives us $ n+2\leq 2+\frac{903\cdot ln(10)}{ln(\frac{(1+\sqrt{5})}{2}}<5000$ so we are done.
08.02.2022 04:24
In the part $a)$, we have that $a_n=f_{n-2}a_1+f_{n-1}a_2$ for each $n\geq 3$,, where $f_i$ is the $n^{\text{th}}$ Fibonacci number. Similarly, we have that $b_n=f_{n-2}b_1+f_{n-1}b_2$. This can be proved by induction. By datum of the problem, we have that $$f_{n-2}b_1+f_{n-1}b_2\mid f_{n-2}a_1+f_{n-1}a_2.$$Therefore, $$f_{n-2}b_1+f_{n-1}b_2\mid b_1(f_{n-2}a_1+f_{n-1}a_2)-a_1(f_{n-2}b_1+f_{n-1}b_2)$$that is, we have that $$f_{n-2}b_1+f_{n-1}b_2\mid f_{n-2}(a_1b_2-a_2b_1).$$Similary, we have that $$f_{n-2}b_1+f_{n-1}b_2\mid f_{n-1}(a_1b_2-a_2b_1).$$subtracting repeatedly, we have that $$f_{n-2}b_1+f_{n-1}b_2\mid a_1b_2-a_2b_1.$$Therefore, $$f_n=f_{n-2}+f_{n-1}\leq f_{n-2}b_1+f_{n-1}b_2\leq \left | a_1b_2-a_2b_1 \right |\leq 1000^2-1<1000^2.$$Let's show that $n<50$. Suppose for the absurd that $n\geq 50$, then $$f_{50}\leq f_n<1000^2.$$it suffices to show that the inequality $f_{50}<1000^2$ is false, for this, we must remember the following equality: $$f_n=\binom{n-1}{0}+\binom{n-2}{1}+\binom{n-2}{3}+\binom{n-3}{4}+\cdots$$it must be fulfilled that $$1251313=\sum_{k=0}^{5}\binom{49-k}{k}<f_{50}<1000^2,$$which is false. Therefore, $n<50$.