Let $a_0$ and $a_n$ be different divisors of a natural number $m$, and $a_0, a_1, \ldots, a_n$ be a sequence of natural numbers such that it satisfies \[a_{i+1} = |a_i\pm a_{i-1}|\text{ for }0 < i < n\] If $gcd(a_0,a_1,\ldots, a_n) = 1$, show that there exists a term of the sequence that is smaller than $\sqrt{m}$ . Proposed by Dusan Djukic
Problem
Source: Serbia NMO 2010 problem 6
Tags: number theory unsolved, number theory
10.06.2017 15:27
who can solve it?
10.06.2017 16:09
Is $a_i$'s are positive numbers? hope so!
10.06.2017 16:23
kd7 wrote: Is $a_i$'s are positive numbers? hope so! Yes positive divisors.
18.12.2017 05:32
Is this right? Suppose the conclusion is false. (1) $(a_0,a_1)=1$. Proof: Easy. (2) Let $r_0=a_0, r_1=a_1, r_{i+1}=|r_{i}-r_{i-1}| (\forall i\geq1)$, then there exists a $j\geq1$ satisfying $r_{i}\geq\sqrt{m} (\forall i\leq j), r_{j+1}<\sqrt{m}$. Proof: Notice that $\{\text{max}\{r_{i-1},r_i\}\}$ is decreasing. (3) Let $s=r_{j-1}, t=r_{j}$, then $(s,t)=1$, and there exist two integer sequences $\{b_i\}, \{c_i\}$ satisfying: (3.1) $a_i=b_is+c_it$; (3.2) $|b_ic_{i-1}-b_{i-1}c_i|=1.$ Therefore, $(b_i, c_i)=1$. Proof: By (1) we get $(s,t)=1$. Induct reversely along $\{r_i\}$, then induct along $\{a_i\}$. (4) $\forall i\geq0$, $b_i$ and $c_i$ satisfy one of three conditions: (4.1) $b_i=0, c_i=1$; (4.2) $b_i=1, c_i=0$; (4.3) $b_i>0, c_i>0$, and $(b_i-b_{i-1})(c_i-c_{i-1})\geq0$ if $i\geq1$. Proof: Induct reversely along $\{r_i\}$, then induct along $\{a_i\}$ using (3.2) and $|s-t|<\sqrt{m}$. (5) $[a_0,a_n]>m$, which is a contradiction. Proof: By $(b_i, c_i)=1$ and $a_n\ne a_0$ we have $b_0c_n-b_nc_0\ne 0$. Let $(a_0,a_n)=d$, then $d|c_na_0-c_0a_n\implies d|(b_0c_n-b_nc_0)s$. Similarly, $d|(b_0c_n-b_nc_0)t$. Therefore, $d\leq|b_0c_n-b_nc_0|$, and we get $[a_0,a_n]\geq\frac{a_0a_n}{|b_0c_n-b_nc_0|}>\frac{(b_0+c_0)(b_n+c_n)}{|b_0c_n-b_nc_0|}m\geq m$ using (4).