Difference between revisions of "2005 AIME II Problems/Problem 4"
m (→See Also) |
|||
| Line 20: | Line 20: | ||
== See Also == | == See Also == | ||
| + | |||
| + | *[[2005 AIME II Problems/Problem 3| Previous problem]] | ||
| + | *[[2005 AIME II Problems/Problem 5| Next problem]] | ||
*[[2005 AIME II Problems]] | *[[2005 AIME II Problems]] | ||
[[Category:Introductory Number Theory Problems]] | [[Category:Introductory Number Theory Problems]] | ||
Revision as of 19:55, 7 September 2006
Problem
Find the number of positive integers that are divisors of at least one of 
Solution
so 
has 
divisors.
so 
has 
divisors.
so 
has 
divisors.
Now, we use the Principle of Inclusion-Exclusion. We have 
total potential divisors so far, but we've overcounted those factors which divide two or more of our three numbers. Thus, we must subtract off the divisors of their pair-wise greatest common divisors.
which has 8 divisors.
which has 8 divisors.
which has 11 divisors.
So now we have 
potential divisors. However, we've now undercounted those factors which divide all three of our numbers. Luckily, we see that the only such factor is 1, so we must add 1 to our previous sum to get an answer of 
.
