Maths Olympiad Prep

Library / /284 of 520

Number theory Difficulty 7.0 National olympiad Prove it

Show that there exist 20092009 consecutive positive integers such that for each of them the ratio between the largest and the smallest prime divisor is more than 20.20.

Solution

1. Define the Primes:
Let p1,p2,,p2009 p_1, p_2, \ldots, p_{2009} be the first 2009 prime numbers. Let q1,q2,,q2009 q_1, q_2, \ldots, q_{2009} be another set of prime numbers such that qi>20pi q_i > 20p_i for all 1i2009 1 \leq i \leq 2009 . This is possible because there are infinitely many primes, and for any prime pi p_i , there exists a prime qi q_i such that qi>20pi q_i > 20p_i .

2. Chinese Remainder Theorem:
By the Chinese Remainder Theorem, there exists an integer a a such that:
a+i0(modpiqi)for all1i2009 a + i \equiv 0 \pmod{p_i q_i} \quad \text{for all} \quad 1 \leq i \leq 2009
This is possible because the moduli p1q1,p2q2,,p2009q2009 p_1 q_1, p_2 q_2, \ldots, p_{2009} q_{2009} are pairwise coprime.

3. Consecutive Integers:
Consider the sequence a+1,a+2,,a+2009 a+1, a+2, \ldots, a+2009 . For each i i in this range, a+i a+i is divisible by piqi p_i q_i . Therefore, the smallest prime divisor of a+i a+i is pi p_i and the largest prime divisor is qi q_i .

4. Ratio of Prime Divisors:
For each a+i a+i , the ratio between the largest and the smallest prime divisor is:
qipi>20 \frac{q_i}{p_i} > 20
This satisfies the condition that the ratio between the largest and the smallest prime divisor is more than 20.

5. Conclusion:
Thus, the sequence a+1,a+2,,a+2009 a+1, a+2, \ldots, a+2009 consists of 2009 consecutive positive integers such that for each of them, the ratio between the largest and the smallest prime divisor is more than 20.

\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.