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"
(→‎Solution (Basic Casework and Combinations))
 
(13 intermediate revisions by 8 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 (Basic Casework and Combinations) ==
−
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>.  
+
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 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 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 50.  There are four of these (2, 3, 5 and 7) and so four numbers of the second 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=109</math> integers that meet the given conditions.
+
Thus there are <math>105+4=\boxed{109}</math> integers that meet the given conditions.
 +
 
 +
 
 +
~lpieleanu (Minor editing)
 +
~ rollover2020 (extremely minor editing)
  
 
== See also ==
 
== See also ==
−
* [[2005 AIME I Problems/Problem 2 | Previous problem]]
 
−
* [[2005 AIME I Problems/Problem 4 | Next problem]]
 
−
* [[2005 AIME I Problems]]
 
 
* [[Divisor_function#Demonstration | Counting divisors of positive integers]]
 
* [[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]]
 
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:37, 23 January 2024

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 $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$ ways to choose a pair of primes from the list and thus $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.


~lpieleanu (Minor editing) ~ rollover2020 (extremely 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. AMC logo.png

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