Difference between revisions of "2005 AIME I Problems/Problem 3"
(A solution to an AIME problem.) |
(→Solution) |
||
| (16 intermediate revisions by 10 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | How many positive | + | 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 (Basic Casework and Combinations) == |
| − | + | 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> ways to choose a pair of primes from the list and thus <math>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. | ||
| + | |||
| + | |||
| + | ~lpieleanu (Minor editing) | ||
== See also == | == See also == | ||
| − | * [[2005 | + | * [[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 11:35, 16 August 2022
Problem
How many positive integers have exactly three proper divisors (positive integral divisors excluding itself), each of which is less than 50?
Solution (Basic Casework and Combinations)
Suppose 
is such an integer. Because has 
proper divisors, it must have 
divisors,, so must be in the form 
or 
for distinct prime numbers 
and 
.
In the first case, the three proper divisors of are 
, and . Thus, we need to pick two prime numbers less than 
. There are fifteen of these (
and 
) so there are 
ways to choose a pair of primes from the list and thus 
numbers of the first type.
In the second case, the three proper divisors of are 1, and 
. Thus we need to pick a prime number whose square is less than . There are four of these (
and 
) and so four numbers of the second type.
Thus there are 
integers that meet the given conditions.
~lpieleanu (Minor editing)
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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
