Difference between revisions of "2000 AIME II Problems/Problem 4"

Latest revision as of 15:55, 11 May 2022

Problem

What is the smallest positive integer with six positive odd integer divisors and twelve positive even integer divisors?

Solution 1

We use the fact that the number of divisors of a number $n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}$ is $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$ . If a number has $18 = 2 \cdot 3 \cdot 3$ factors, then it can have at most $3$ distinct primes in its factorization.

Dividing the greatest power of $2$ from $n$ , we have an odd integer with six positive divisors, which indicates that it either is ( $6 = 2 \cdot 3$ ) a prime raised to the $5$ th power, or two primes, one of which is squared. The smallest example of the former is $3^5 = 243$ , while the smallest example of the latter is $3^2 \cdot 5 = 45$ .

Suppose we now divide all of the odd factors from $n$ ; then we require a power of $2$ with $\frac{18}{6} = 3$ factors, namely $2^{3-1} = 4$ . Thus, our answer is $2^2 \cdot 3^2 \cdot 5 = \boxed{180}$ .

Solution 2

Somewhat similar to the first solution, we see that the number $n$ has two even factors for every odd factor. Thus, if $x$ is an odd factor of $n$ , then $2x$ and $4x$ must be the two corresponding even factors. So, the prime factorization of $n$ is $2^2 3^a 5^b 7^c...$ for some set of integers $a, b, c, ...$

Since there are $18$ factors of $n$ , we can write:

$(2+1)(a+1)(b+1)(c+1)... = 18$

$(a+1)(b+1)(c+1)... = 6$

Since $6$ only has factors from the set $1, 2, 3, 6$ , either $a=5$ and all other variables are $0$ , or $a=3$ and $b=2$ , with again all other variables equal to $0$ . This gives the two numbers $2^2 \cdot 3^5$ and $2^2 \cdot 3^2 \cdot 5$ . The latter number is smaller, and is equal to $\boxed {180}$ .

Solution 3

We see that the least number with 6 odd factors is $3^2*5$ . Multiplied by $2^2$ (as each factor of 2 doubles the odd factors, as it can be 2n or $2^2n$ . Finally, you get $180$

-dragoon

@@ Line 2: / Line 2: @@
 What is the smallest positive integer with six positive odd integer divisors and twelve positive even integer divisors?
-== Solution ==
+== Solution 1==
-If a number has 18 divisors, then the prime factorization of the number must contain at most 3 distinct primes (since <math>18=3*3*2</math>).The number obviously cannot have only 1 prime.
+We use the fact that the number of divisors of a number <math>n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}</math> is <math>(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)</math>. If a number has <math>18 = 2 \cdot 3 \cdot 3</math> factors, then it can have at most <math>3</math> distinct primes in its factorization.
+Dividing the greatest power of <math>2</math> from <math>n</math>, we have an odd integer with six positive divisors, which indicates that it either is (<math>6 = 2 \cdot 3</math>) a prime raised to the <math>5</math>th power, or two primes, one of which is squared. The smallest example of the former is <math>3^5 = 243</math>, while the smallest example of the latter is <math>3^2 \cdot 5 = 45</math>.
-If the number has two primes, then one of the primes must be odd and the other even. Since there must be 6 odd divisors, the odd prime must be raised to the 5th power. The even prime would be raised to 2nd power, so that the total number of divisors is 18. The smallest number that satisfies those conditions is <math>3^5*2^2=972</math>
+Suppose we now divide all of the odd factors from <math>n</math>; then we require a power of <math>2</math> with <math>\frac{18}{6} = 3</math> factors, namely <math>2^{3-1} = 4</math>. Thus, our answer is <math>2^2 \cdot 3^2 \cdot 5 = \boxed{180}</math>.
+== Solution 2 ==
+Somewhat similar to the first solution, we see that the number <math>n</math> has two even factors for every odd factor.  Thus, if <math>x</math> is an odd factor of <math>n</math>, then <math>2x</math> and <math>4x</math> must be the two corresponding even factors.  So, the prime factorization of <math>n</math> is <math>2^2 3^a 5^b 7^c...</math> for some set of integers <math>a, b, c, ...</math>
-If the number has three primes, then two of them must be raised to the 2nd power and the other one of them must be raised to the first. To get 6 odd divisors, we need two odd primes; one that is raised to the 2nd power and one that is raised to the first. Then, to get 18 total divisors, we need an even prime that is raised to the 2nd power. The smallest number that satisfies those conditions is <math>2^2*3^2*5=180</math>
+Since there are <math>18</math> factors of <math>n</math>, we can write:
+<math>(2+1)(a+1)(b+1)(c+1)... = 18</math>
-Therefore, the smallest integer is <math>180</math>
+<math>(a+1)(b+1)(c+1)... = 6</math>
+Since <math>6</math> only has factors from the set <math>1, 2, 3, 6</math>, either <math>a=5</math> and all other variables are <math>0</math>, or <math>a=3</math> and <math>b=2</math>, with again all other variables equal to <math>0</math>.  This gives the two numbers <math>2^2 \cdot 3^5</math> and <math>2^2 \cdot 3^2 \cdot 5</math>.  The latter number is smaller, and is equal to <math>\boxed {180}</math>.
+==Solution 3==
+We see that the least number with 6 odd factors is <math>3^2*5</math>. Multiplied by <math>2^2</math> (as each factor of 2 doubles the odd factors, as it can be 2n or <math>2^2n</math>. Finally, you get <math>180</math>
+-dragoon
 == See also ==
 {{AIME box|year=2000|n=II|num-b=3|num-a=5}}
+[[Category:Intermediate Number Theory Problems]]
+{{MAA Notice}}

2000 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search