Mock AIME 1 2007-2008 Problems/Problem 9

Problem 9

Let $n$ represent the smallest integer that satisfies the following conditions:

$\frac n2$ is a perfect square.
$\frac n3$ is a perfect cube.
$\frac n5$ is a perfect fifth.

How many divisors does $n$ have that are not multiples of 10?

Solution

The first condition implies that the power of each prime factor of $n$ must be an even power (excluding $2$, which must be an odd power). The second condition implies that the power of each prime factor of $n$ must be divisible by $3$ (excluding $3$, which must leave a residue of $1$ upon division by $3$). The third condition implies that the power of each prime factor of $n$ must be divisible by $5$ (excluding $5$, which must leave a residue of $1$ upon division by $5$).

Clearly, to minimize $n$, we want to just use the prime factors $2,3,5$. The power of $2$ must be divisible by $3,5$, and $2^{15}$ works. Similarly, the powers of $3$ and $5$ must be $10$ and $6$, respectively, both of which leave a residue of $1$ upon division. Thus, we need the number of factors of $2^{15} \cdot 3^{10} \cdot 5^{6}$ which are not multiples of $10$.

Applying the complement principle, there are a total of $(15+1)(10+1)(6+1) = 1232$ factors. We can draw a bijection between the number of divisors of $2^{15} \cdot 3^{10} \cdot 5^{6}$ that are divisible by $10$ and the number of divisors of $2^{14} \cdot 3^{10} \cdot 5^{5}$ (as each of these divisors, when multiplied by 10, will provide a factor of the original number that is divisible by 10). There are $(14+1)(10+1)(5+1) = 990$. The answer is $1232-990 = \boxed{242}$.

See also

Mock AIME 1 2007-2008 (Problems, Source)
Preceded by
Problem 8
Followed by
Problem 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15