Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(rewrite)
m (→‎Solution 3)
 
(5 intermediate revisions by 5 users not shown)
Line 2: Line 2:
 
What is the smallest positive integer with six positive odd integer divisors and twelve positive even integer divisors?
 
What is the smallest positive integer with six positive odd integer divisors and twelve positive even integer divisors?
  
−
== Solution ==
+
== Solution 1==
−
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 2 \cdot 3</math> factors, then it can have at most <math>3</math> distinct primes in its factorization.  
+
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>.  
 
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>.  
  
 
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>.
 
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>
 +
 +
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>
 +
 +
<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 ==
 
== See also ==
Line 13: Line 30:
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 14: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

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_II_Problems/Problem_4&oldid=173879"