Maths Olympiad Prep

Library / /45 of 60

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Prove that for any positive integer kk, there exists an arithmetic sequence
a1b1,a2b2,,akbk \frac{a_{1}}{b_{1}}, \quad \frac{a_{2}}{b_{2}}, \quad \ldots, \quad \frac{a_{k}}{b_{k}}
of rational numbers, where ai,bia_{i}, b_{i} are relatively prime positive integers for each i=1,2,,ki=1,2, \ldots, k, such that the positive integers a1,b1,a2,b2,,ak,bka_{1}, b_{1}, a_{2}, b_{2}, \ldots, a_{k}, b_{k} are all distinct.

Solutions — 2

Solution 1

For k=1k=1, there is nothing to prove. Henceforth assume k2k \geq 2.
Let p1,p2,,pkp_{1}, p_{2}, \ldots, p_{k} be kk distinct primes such that
k<pk<<p2<p1 k < p_{k} < \cdots < p_{2} < p_{1}
and let N=p1p2pkN = p_{1} p_{2} \cdots p_{k}. By Chinese Remainder Theorem, there exists a positive integer xx satisfying
xi(mod pi) x \equiv -i \quad (\bmod\ p_{i})
for all i=1,2,,ki=1,2, \ldots, k and x>N2x > N^{2}. Consider the following sequence:
x+1N,x+2N,,x+kN. \frac{x+1}{N}, \quad \frac{x+2}{N}, \quad \ldots, \quad \frac{x+k}{N}.
This sequence is obviously an arithmetic sequence of positive rational numbers of length kk. For each i=1,2,,ki=1,2, \ldots, k, the numerator x+ix+i is divisible by pip_{i} but not by pjp_{j} for jij \neq i, for otherwise pjp_{j} divides ij|i-j|, which is not possible because pj>k>ijp_{j} > k > |i-j|. Let
ai:=x+ipi,bi:=Npi for all i=1,2,,k a_{i} := \frac{x+i}{p_{i}}, \quad b_{i} := \frac{N}{p_{i}} \quad \text{ for all } i=1,2, \ldots, k
Then
x+iN=aibi,gcd(ai,bi)=1 for all i=1,2,,k \frac{x+i}{N} = \frac{a_{i}}{b_{i}}, \quad \operatorname{gcd}(a_{i}, b_{i}) = 1 \quad \text{ for all } i=1,2, \ldots, k
and all bib_{i}'s are distinct from each other. Moreover, x>N2x > N^{2} implies
ai=x+ipi>N2pi>N>Npj=bj for all i,j=1,2,,k a_{i} = \frac{x+i}{p_{i}} > \frac{N^{2}}{p_{i}} > N > \frac{N}{p_{j}} = b_{j} \quad \text{ for all } i, j = 1,2, \ldots, k
and hence all aia_{i}'s are distinct from bib_{i}'s. It only remains to show that all aia_{i}'s are distinct from each other. This follows from
aj=x+jpj>x+ipj>x+ipi=ai for all i<j a_{j} = \frac{x+j}{p_{j}} > \frac{x+i}{p_{j}} > \frac{x+i}{p_{i}} = a_{i} \quad \text{ for all } i < j
by our choice of p1,p2,,pkp_{1}, p_{2}, \ldots, p_{k}. Thus, the arithmetic sequence
a1b1,a2b2,,akbk \frac{a_{1}}{b_{1}}, \quad \frac{a_{2}}{b_{2}}, \quad \ldots, \quad \frac{a_{k}}{b_{k}}
of positive rational numbers satisfies the conditions of the problem.

Solution 2

For any positive integer k2k \geq 2, consider the sequence
(k!)2+1k!,(k!)2+2k!,,(k!)2+kk! \frac{(k!)^{2}+1}{k!}, \frac{(k!)^{2}+2}{k!}, \ldots, \frac{(k!)^{2}+k}{k!}
Note that gcd(k!,(k!)2+i)=i\operatorname{gcd}(k!, (k!)^{2}+i) = i for all i=1,2,,ki=1,2, \ldots, k. So, taking
ai:=(k!)2+ii,bi:=k!i for all i=1,2,,k a_{i} := \frac{(k!)^{2}+i}{i}, \quad b_{i} := \frac{k!}{i} \quad \text{ for all } i=1,2, \ldots, k
we have gcd(ai,bi)=1\operatorname{gcd}(a_{i}, b_{i}) = 1 and
ai=(k!)2+ii>aj=(k!)2+jj>bi=k!i>bj=k!j a_{i} = \frac{(k!)^{2}+i}{i} > a_{j} = \frac{(k!)^{2}+j}{j} > b_{i} = \frac{k!}{i} > b_{j} = \frac{k!}{j}
for any 1i<jk1 \leq i < j \leq k. Therefore this sequence satisfies every condition given in the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.