Olympiad Maths Prep

Track / Stage 8 / 143 of 180 #1843 of 2000

Problem 1843

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.6 Prove it Team selection tests for IMO 2018 · Saudi Arabia · 2018

Consider the infinite, strictly increasing sequence of positive integers ana_{n} such that

i. All terms of the sequence are pairwise coprime.

ii. The sum 1a1a2+1a2a3+1a3a4+\frac{1}{\sqrt{a_{1} a_{2}}} + \frac{1}{\sqrt{a_{2} a_{3}}} + \frac{1}{\sqrt{a_{3} a_{4}}} + \cdots is unbounded.

Prove that this sequence contains infinitely many primes.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Suppose on the contrary that there are infinite primes in this sequence, thus there is some index kk such that ana_{n} is composite for all n>kn > k. Denote SS as all prime divisors of the first kk terms of the given sequence.

By comparing ak+1a_{k+1} with the first prime p1p_{1} that does not appear in SS then we have ak+1p12a_{k+1} \geq p_{1}^{2} (since ak+1a_{k+1} is composite and p1p_{1} is not greater than the least prime divisor of this number).

Similarly, define p2p_{2} as the second prime that does not appear in SS then ak+2p22a_{k+2} \geq p_{2}^{2} (since all terms of the sequence are pairwise coprime). In general, we get
ak+ipi2 for all iZ+. a_{k+i} \geq p_{i}^{2} \text{ for all } i \in \mathbb{Z}^{+} .

Note that 1ak+1ak+2<1ak+11p12\frac{1}{\sqrt{a_{k+1} a_{k+2}}} < \frac{1}{a_{k+1}} \leq \frac{1}{p_{1}^{2}}, 1ak+2ak+3<1ak+21p22\frac{1}{\sqrt{a_{k+2} a_{k+3}}} < \frac{1}{a_{k+2}} \leq \frac{1}{p_{2}^{2}}, \cdots and so on. Then the given sum in the second condition can be divided into two parts: the first is the sum taken on values from a1,a2,,aka_{1}, a_{2}, \ldots, a_{k} which is finite, and the second is less than
1p12+1p22+<112+122+132+<1+112+123+=(112)+(1213)+(1314)<2. \begin{aligned} \frac{1}{p_{1}^{2}} + \frac{1}{p_{2}^{2}} + \cdots &< \frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \cdots < 1 + \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots \\ &= \left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{4}\right) < 2 . \end{aligned}

Hence, the given sum is bounded, which is a contradiction and this finishes our proof.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.