Difference between revisions of "2005 AIME I Problems/Problem 3"

 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
How many [[positive integer]]s have exactly three [[proper divisor]]s, each of which is less than 50?
+
How many [[positive integer]]s have exactly three [[proper divisor]]s (positive integral [[divisor]]s excluding itself), each of which is less than 50?
  
 
== 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]]. Because <math>n</math> has <math>3</math> proper divisors, it must have <math>4</math> divisors,, 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>.  
 +
 
 +
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 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 <math>50</math>.  There are four of these (<math>2, 3, 5</math> and <math>7</math>) and so four numbers of the second type.  
 +
 
 +
Thus there are <math>105+4=\boxed{109}</math> integers that meet the given conditions.
  
 
== See also ==
 
== See also ==
* [[2005 AIME I Problems/Problem 2 | Previous problem]]
+
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
* [[2005 AIME I Problems/Problem 4 | Next problem]]
+
{{AIME box|year=2005|n=I|num-b=2|num-a=4}}
* [[2005 AIME I Problems]]
 
  
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 14:26, 7 November 2019

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. Because $n$ has $3$ proper divisors, it must have $4$ divisors,, so $n$ must be in the form $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=\boxed{109}$ integers that meet the given conditions.

See also

2005 AIME I (ProblemsAnswer KeyResources)
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

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

Invalid username
Login to AoPS