For any positive integer , let denote the number of different prime divisors of the number . (For instance, .) Show that there exist infinitely many positive integers such that .
Solution
1. We need to show that there exist infinitely many positive integers such that . Here, denotes the number of different prime divisors of .
2. Consider the sequence . We will show that for sufficiently large , this sequence satisfies .
3. First, note that has only one prime divisor, which is 2. Therefore, .
4. Next, consider . For large , is not a power of 2 and is not divisible by 2. Therefore, it must have at least one prime divisor other than 2. Hence, .
5. Now, consider . Since is odd, it must have at least one prime divisor other than 2. Therefore, .
6. To ensure , we need to show that has at least one prime divisor that does not have. For sufficiently large , this is generally true because the distribution of prime numbers ensures that and will have different sets of prime divisors.
7. Therefore, for sufficiently large , we have:
This implies:
8. Since can be chosen to be arbitrarily large, there are infinitely many such that satisfy the condition.