Maths Olympiad Prep

Library / /494 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Let NN be the number of triples of positive integers (a,b,c)(a, b, c) satisfying abc,gcd(a,b,c)=1,abc=62020a \leq b \leq c, \quad \operatorname{gcd}(a, b, c)=1, \quad a b c=6^{2020}. Compute the remainder when NN is divided by 1000.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n=2020n=2020. If we let a=2p13q1,b=2p23q2,c=2p33q3a=2^{p_{1}} \cdot 3^{q_{1}}, b=2^{p_{2}} \cdot 3^{q_{2}}, c=2^{p_{3}} \cdot 3^{q_{3}}, then the number of ordered triples (a,b,c)(a, b, c) that satisfy the second and third conditions is the number of nonnegative solutions to p1+p2+p3=np_{1}+p_{2}+p_{3}=n and q1+q2+q3=nq_{1}+q_{2}+q_{3}=n, where at least one of p1,p2,p3p_{1}, p_{2}, p_{3} is zero and at least one of q1,q2,q3q_{1}, q_{2}, q_{3} is zero (otherwise, gcd(a,b,c)>1\operatorname{gcd}(a, b, c)>1). By complementary counting, the number is ((n+22)(n12))2=9n2\left(\binom{n+2}{2}-\binom{n-1}{2}\right)^{2}=9 n^{2} Let \ell be the number of unordered triples (a,b,c)(a, b, c) with a,b,ca, b, c distinct, and mm the number of unordered triples (a,b,c)(a, b, c) with two numbers equal. Since it is impossible for a=b=ca=b=c, we have 9n2=6+3m9 n^{2}=6 \ell+3 m. We now count mm. Without loss of generality, assume a=ba=b. For the factors of 2, we have two choices: either assign 220202^{2020} to cc or assign 210102^{1010} to both aa and bb. We have a similar two choices for the factors of 3. Therefore m=4m=4. Our final answer is N=m+n=6+3m+3m6=920202+126=2+610102602(mod1000)N=m+n=\frac{6 \ell+3 m+3 m}{6}=\frac{9 \cdot 2020^{2}+12}{6}=2+6 \cdot 1010^{2} \equiv 602 \quad(\bmod 1000)

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.