Number theoryDifficulty 7.1National olympiad, round 2Prove it
Consider the infinite, strictly increasing sequence of positive integer (an) such that i. All terms of sequences are pairwise coprime. ii. The sum a1a21+a2a31+a3a41+.. is unbounded. Prove that this sequence contains infinitely many primes.
Solution
1. Assume the contrary: Suppose that after some index k, all terms ak+i are composite numbers. This means there exists an index k such that for all i≥1, ak+i is composite.
2. **Sum starting from ak**: Since the sum a1a21+a2a31+a3a41+⋯ is unbounded, the sum starting from ak should also be unbounded. Let's denote this sum by T: T=akak+11+ak+1ak+21+ak+2ak+31+⋯
3. **Bounding the sum T**: Since all ak+i are composite, each ak+i has at least two prime divisors. Therefore, we can write: ak+i≥p1p2 where p1 and p2 are the smallest prime factors of ak+i. This implies: ak+iak+i+1≥(p1p2)(p3p4)≥2⋅3⋅2⋅3=6 Hence, ak+iak+i+11≤61
4. Comparing with a known series: Consider the series: 2⋅31+3⋅41+4⋅51+⋯ This series can be written as: n=2∑∞n(n+1)1 Using partial fractions, we have: n(n+1)1=n1−n+11 Therefore, the series telescopes: n=2∑∞(n1−n+11)=(21−31)+(31−41)+(41−51)+⋯=21
5. **Bounding T**: Since ak+iak+i+11≤61, we have: T<n=2∑∞n(n+1)1=21 This implies that T is bounded by 21.
6. Contradiction: The assumption that T is bounded contradicts the given condition that the sum is unbounded. Therefore, our initial assumption that all ak+i are composite must be false.
7. Conclusion: Hence, the sequence (an) must contain infinitely many primes.
■
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.