Mock AIME 1 2007-2008 Problems/Problem 9

From AoPSWiki

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 not divisible by $10$ and the number of divisors of $2^{14} \cdot 3^{10} \cdot 5^{5}$ , of which there are $(14+1)(10+1)(5+1) = 990$ . The answer is $1232-990 = \boxed{242}$ .

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

Personal tools

Navigation

Search

Toolbox

Mock AIME 1 2007-2008 Problems/Problem 9

From AoPSWiki

Problem 9

Solution

See also