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 "2005 AIME I Problems/Problem 3"
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
<math>n=p\cdot q</math> or <math>n=p^3</math> where p and q are distinct primes. In the first case, the three proper divisors of n are 1, p, and q. Because there are 15 prime numbers less than 50, there are <math> {15 \choose 2} =105</math> numbers of the first type.There are four integers of the second type because 2, 3, 5, and 7 are the only primes with squares less than 50. Thus there are <math>105+4=109</math> integers that meet the given conditions.
+
Suppose <math>n</math> is such an [[integer]].  Then <math>n=p\cdot q</math> or <math>n=p^3</math> for distinct [[prime number]]s <math>p</math> and <math>q</math>.  
 +
 
 +
In the first case, the three proper divisors of <math>n</math> are 1, <math>p</math> and <math>q</math>. Thus, we need to pick two prime numbers less than 50.  There are fifteen of these (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47) so there are <math> {15 \choose 2} =105</math> numbers of the first type.
 +
 
 +
In the second case, the three proper divisors of <math>n</math> are 1, <math>p</math> and <math>p^2</math>.  Thus we need to pick a prime number whose square is less than 50.  There are four of these (2, 3, 5 and 7) and so four numbers of the second type.  
 +
 
 +
Thus there are <math>105+4=109</math> integers that meet the given conditions.
  
 
== See also ==
 
== See also ==
Line 9: Line 15:
 
* [[2005 AIME I Problems/Problem 4 | Next problem]]
 
* [[2005 AIME I Problems/Problem 4 | Next problem]]
 
* [[2005 AIME I Problems]]
 
* [[2005 AIME I Problems]]
−
 
+
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]

Revision as of 11:43, 29 November 2006

Problem

How many positive integers have exactly three proper divisors, each of which is less than 50?

Solution

Suppose $n$ is such an integer. Then $n=p\cdot q$ or $n=p^3$ for distinct prime numbers $p$ and $q$.

In the first case, the three proper divisors of $n$ are 1, $p$ and $q$. Thus, we need to pick two prime numbers less than 50. There are fifteen of these (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47) so there are ${15 \choose 2} =105$ numbers of the first type.

In the second case, the three proper divisors of $n$ are 1, $p$ and $p^2$. Thus we need to pick a prime number whose square is less than 50. There are four of these (2, 3, 5 and 7) and so four numbers of the second type.

Thus there are $105+4=109$ integers that meet the given conditions.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_3&oldid=11878"