Maths Olympiad Prep

Library / /496 of 520

Number theory Difficulty 4.4 AIME Find the answer

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1010=21051010^{10} = 2^{10}\cdot 5^{10} so 101010^{10} has 1111=12111\cdot11 = 121 divisors.
157=375715^7 = 3^7\cdot5^7 so 15715^7 has 88=648\cdot8 = 64 divisors.
1811=21132218^{11} = 2^{11}\cdot3^{22} so 181118^{11} has 1223=27612\cdot23 = 276 divisors.
Now, we use the Principle of Inclusion-Exclusion. We have 121+64+276121 + 64 + 276 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.
gcd(1010,157)=57\gcd(10^{10},15^7) = 5^7 which has 8 divisors.
gcd(157,1811)=37\gcd(15^7, 18^{11}) = 3^7 which has 8 divisors.
gcd(1811,1010)=210\gcd(18^{11}, 10^{10}) = 2^{10} which has 11 divisors.
So now we have 121+64+2768811121 + 64 + 276 - 8 -8 -11 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 121+64+2768811+1=435121 + 64 + 276 - 8 - 8 - 11 + 1 = \boxed{435}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.