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"

m ((minor) tex)
(Fix: n should equal p^2, not p^3)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
Suppose <math>n</math> is such an [[integer]]. Then one of its factors is <math>1</math>, so <math>n</math> must be in the form <math>n=p\cdot q</math> or <math>n=p^3</math> for distinct [[prime number]]s <math>p</math> and <math>q</math>.  
+
Suppose <math>n</math> is such an [[integer]]. Then one of its factors is <math>1</math>, so <math>n</math> must be in the form <math>n=p\cdot q</math> or <math>n=p^2</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 <math>1</math>, <math>p</math> and <math>q</math>.  Thus, we need to pick two prime numbers less than <math>50</math>. There are fifteen of these (<math>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43</math> and <math>47</math>) so there are <math> {15 \choose 2} =105</math> numbers of the first type.
 
In the first case, the three proper divisors of <math>n</math> are <math>1</math>, <math>p</math> and <math>q</math>.  Thus, we need to pick two prime numbers less than <math>50</math>. There are fifteen of these (<math>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43</math> and <math>47</math>) so there are <math> {15 \choose 2} =105</math> numbers of the first type.

Revision as of 22:25, 7 March 2009

Problem

How many positive integers have exactly three proper divisors (positive integral divisors excluding itself), each of which is less than 50?

Solution

Suppose $n$ is such an integer. Then one of its factors is $1$, so $n$ must be in the form $n=p\cdot q$ or $n=p^2$ 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=\boxed{109}$ integers that meet the given conditions.

See also

2005 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_3&oldid=30624"