For any positive integer , let be all the positive divisors of , where . If there exist integers such that , then we say that is a good number. Prove that there exists a good number with exactly 2013 distinct prime factors.
Solution
We say that a positive integer is excellent if it is good, and we can find integers such that . Let be distinct primes larger than 3. We prove by induction on that the integer is excellent.
For the base case , the positive divisors of are , , , . Since we have and , the integer is excellent.
For the inductive step, assume is excellent. Let be all of its positive divisors, and let
Consider . Its positive divisors are of the form and . Note that
Also, we have
Therefore, is excellent. By induction, our claim holds. In particular, we can take so that is excellent, and hence it is a good integer with exactly 2013 prime divisors.
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.