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

(Typesetting : don't put math tags around dollar signs; dollar sign=math tag. Also, you have to do {n \choose k} on the wiki instead of \binom{n}{k})
(11 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
How many positive integers have exactly three proper divisors, 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 ==
Having three proper divisors means that there are 4 regular divisors. So the number can be written as <math>\displaystyle p_{1}p_{2}</math> where <math>\displaystyle p_{1}</math> and <math>\displaystyle p_{2}</math> are primes. The primes under fifty are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. There are 15 of them. So there are <math> {15 \choose 2} =105</math> such numbers.
+
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]]
+
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
 +
{{AIME box|year=2005|n=I|num-b=2|num-a=4}}
 +
 
 +
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

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