Maths Olympiad Prep

Library / /11 of 11

, 2018

Number theory Difficulty 8.6 Shortlist Prove it Saudi Arabia

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.

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.

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.