Maths Olympiad Prep

Library / /344 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Prove it

Consider the infinite, strictly increasing sequence of positive integer (an)(a_n) such that
i. All terms of sequences are pairwise coprime.
ii. The sum 1a1a2+1a2a3+1a3a4+..\frac{1}{\sqrt{a_1a_2}} +\frac{1}{\sqrt{a_2a_3}}+ \frac{1}{\sqrt{a_3a_4}} + .. is unbounded.
Prove that this sequence contains infinitely many primes.

Solution

1. Assume the contrary: Suppose that after some index k k , all terms ak+i a_{k+i} are composite numbers. This means there exists an index k k such that for all i1 i \geq 1 , ak+i a_{k+i} is composite.

2. **Sum starting from ak a_k **: Since the sum
1a1a2+1a2a3+1a3a4+ \frac{1}{\sqrt{a_1a_2}} + \frac{1}{\sqrt{a_2a_3}} + \frac{1}{\sqrt{a_3a_4}} + \cdots
is unbounded, the sum starting from ak a_k should also be unbounded. Let's denote this sum by T T :
T=1akak+1+1ak+1ak+2+1ak+2ak+3+ T = \frac{1}{\sqrt{a_k a_{k+1}}} + \frac{1}{\sqrt{a_{k+1} a_{k+2}}} + \frac{1}{\sqrt{a_{k+2} a_{k+3}}} + \cdots

3. **Bounding the sum T T **: Since all ak+i a_{k+i} are composite, each ak+i a_{k+i} has at least two prime divisors. Therefore, we can write:
ak+ip1p2 a_{k+i} \geq p_1 p_2
where p1 p_1 and p2 p_2 are the smallest prime factors of ak+i a_{k+i} . This implies:
ak+iak+i+1(p1p2)(p3p4)2323=6 \sqrt{a_{k+i} a_{k+i+1}} \geq \sqrt{(p_1 p_2)(p_3 p_4)} \geq \sqrt{2 \cdot 3 \cdot 2 \cdot 3} = 6
Hence,
1ak+iak+i+116 \frac{1}{\sqrt{a_{k+i} a_{k+i+1}}} \leq \frac{1}{6}

4. Comparing with a known series: Consider the series:
123+134+145+ \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots
This series can be written as:
n=21n(n+1) \sum_{n=2}^{\infty} \frac{1}{n(n+1)}
Using partial fractions, we have:
1n(n+1)=1n1n+1 \frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}
Therefore, the series telescopes:
n=2(1n1n+1)=(1213)+(1314)+(1415)+=12 \sum_{n=2}^{\infty} \left( \frac{1}{n} - \frac{1}{n+1} \right) = \left( \frac{1}{2} - \frac{1}{3} \right) + \left( \frac{1}{3} - \frac{1}{4} \right) + \left( \frac{1}{4} - \frac{1}{5} \right) + \cdots = \frac{1}{2}

5. **Bounding T T **: Since 1ak+iak+i+116 \frac{1}{\sqrt{a_{k+i} a_{k+i+1}}} \leq \frac{1}{6} , we have:
T<n=21n(n+1)=12 T < \sum_{n=2}^{\infty} \frac{1}{n(n+1)} = \frac{1}{2}
This implies that T T is bounded by 12 \frac{1}{2} .

6. Contradiction: The assumption that T T is bounded contradicts the given condition that the sum is unbounded. Therefore, our initial assumption that all ak+i a_{k+i} are composite must be false.

7. Conclusion: Hence, the sequence (an) (a_n) must contain infinitely many primes.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.