Browse · MATH
Printjmc
number theory senior
Problem
Suppose and are positive integers such that is divisible by exactly distinct primes and is divisible by exactly distinct primes.
If has fewer distinct prime factors than , then has at most how many distinct prime factors?
If has fewer distinct prime factors than , then has at most how many distinct prime factors?
Solution
The prime factors of are precisely the prime factors which are common to and (i.e., the primes that divide both). The prime factors of are the primes which divide at least one of and .
Thus, there are primes which divide both and , and more primes which divide exactly one of and . Since has fewer distinct prime factors than , we know that fewer than half of these primes divide ; at most, of these primes divide . So, has at most distinct prime factors.
Thus, there are primes which divide both and , and more primes which divide exactly one of and . Since has fewer distinct prime factors than , we know that fewer than half of these primes divide ; at most, of these primes divide . So, has at most distinct prime factors.
Final answer
17