Number theoryDifficulty 6.8Prove itIranian Mathematical Olympiad · Iran
For two rational numbers r,s we say r∣s if there is k∈Z so that s=kr. The sequence (an)n∈N is an increasing sequence of natural numbers such that for all i,j∈N, gcd(ai,aj)=1 and (bn)n∈N is a sequence of distinct natural numbers. Assume that for each n∈N we have i=1∑nai1∣i=1∑nbi1, prove that for all n∈N we have an=bn.
This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.
i=1∑nbi1=kni=1∑nai1 by subtracting these equalities for n,n+1 we have: bn+11=kn+1an+11+(kn+1−kn)i=1∑nai1 Choose a big enough m, such that for n>m we have bn>a0, (this is possible because bi are distinct natural numbers). Then we have bn+11<∑i=1nai1. Therefore kn+1≤kn. Whence, for big enough i, the sequence ki is decreasing, hence they are constant after some point. If kn=kn+1 then because gcd(an+1,an)=1 we have kn=kn+1=1. So we have an=bn for large enough n. Assume that for n>N, an=bn, kn=1, by subtracting the equations i=1∑N+1bi1=i=1∑N+1ai1,aN+1=bN+1 we get ∑i=1Nbi1=∑i=1Nai1 and so kN=1. Now we have bN1=aN1+(1−kN−1)i=1∑N−1ai1 the ai are increasing so if kN−1=1 the right hand side becomes negative which is a contradiction. Hence we have kN−1=1 and by induction, we prove that ai=bi. ■
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.