2005 AIME II Problem 4

Below is the professionally curated solution for Problem 4 of the 2005 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2005 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:factor countinginclusion-exclusiongreatest common divisor

Difficulty rating: 2230

4.

Find the number of positive integers that are divisors of at least one of 1010,10^{10}, 157,15^7, 1811.18^{11}.

Solution:

From the factorizations 1010=210510,10^{10} = 2^{10} 5^{10}, 157=3757,15^7 = 3^7 5^7, and 1811=211322,18^{11} = 2^{11} 3^{22}, the divisor counts are 1111=121,11 \cdot 11 = 121, 88=64,8 \cdot 8 = 64, and 1223=276.12 \cdot 23 = 276.

The divisors common to two of the numbers are exactly the divisors of their gcd: gcd(1010,157)=57\gcd(10^{10}, 15^7) = 5^7 has 88 divisors, gcd(1010,1811)=210\gcd(10^{10}, 18^{11}) = 2^{10} has 11,11, and gcd(157,1811)=37\gcd(15^7, 18^{11}) = 3^7 has 8.8. Only 11 divides all three numbers.

By inclusion-exclusion, the count is 121+64+2768118+1=435.121 + 64 + 276 - 8 - 11 - 8 + 1 = 435.

← Problem 3Full ExamProblem 5

Problem 4 in Other Years