Difference between revisions of "Mock AIME 1 2007-2008 Problems/Problem 9"
Armalite46 (talk | contribs) m (→Solution) |
m (→Solution) |
||
Line 13: | Line 13: | ||
Clearly, to minimize <math>n</math>, we want to just use the prime factors <math>2,3,5</math>. The power of <math>2</math> must be divisible by <math>3,5</math>, and <math>2^{15}</math> works. Similarly, the powers of <math>3</math> and <math>5</math> must be <math>10</math> and <math>6</math>, respectively, both of which leave a residue of <math>1</math> upon division. Thus, we need the number of factors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> which are not multiples of <math>10</math>. | Clearly, to minimize <math>n</math>, we want to just use the prime factors <math>2,3,5</math>. The power of <math>2</math> must be divisible by <math>3,5</math>, and <math>2^{15}</math> works. Similarly, the powers of <math>3</math> and <math>5</math> must be <math>10</math> and <math>6</math>, respectively, both of which leave a residue of <math>1</math> upon division. Thus, we need the number of factors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> which are not multiples of <math>10</math>. | ||
− | Applying the [[complement principle]], there are a total of <math>(15+1)(10+1)(6+1) = 1232</math> factors. We can draw a bijection between the number of divisors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> that are divisible by <math>10</math> and the number of divisors of <math>2^{14} \cdot 3^{10} \cdot 5^{5}</math>, of | + | Applying the [[complement principle]], there are a total of <math>(15+1)(10+1)(6+1) = 1232</math> factors. We can draw a bijection between the number of divisors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> that are divisible by <math>10</math> and the number of divisors of <math>2^{14} \cdot 3^{10} \cdot 5^{5}</math> (as each of these divisors, when multiplied by 10, will provide a factor of the original number that is divisible by 10). There are <math>(14+1)(10+1)(5+1) = 990</math>. The answer is <math>1232-990 = \boxed{242}</math>. |
== See also == | == See also == |
Latest revision as of 00:32, 31 August 2015
Problem 9
Let represent the smallest integer that satisfies the following conditions:
- is a perfect square.
- is a perfect cube.
- is a perfect fifth.
How many divisors does have that are not multiples of 10?
Solution
The first condition implies that the power of each prime factor of must be an even power (excluding , which must be an odd power). The second condition implies that the power of each prime factor of must be divisible by (excluding , which must leave a residue of upon division by ). The third condition implies that the power of each prime factor of must be divisible by (excluding , which must leave a residue of upon division by ).
Clearly, to minimize , we want to just use the prime factors . The power of must be divisible by , and works. Similarly, the powers of and must be and , respectively, both of which leave a residue of upon division. Thus, we need the number of factors of which are not multiples of .
Applying the complement principle, there are a total of factors. We can draw a bijection between the number of divisors of that are divisible by and the number of divisors of (as each of these divisors, when multiplied by 10, will provide a factor of the original number that is divisible by 10). There are . The answer is .
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 |