Olympiad Maths Prep

Track / Stage 5 / 167 of 400 #767 of 2000

Problem 767

AIME late
Number theory Difficulty 5.4 Find the answer

Example 4 (Problem from the 5th American Invitational Mathematics Examination) Let [r,s][r, s] denote the least common multiple of the positive integers r,sr, s. Find the number of ordered triples (a,b,c)(a, b, c) such that [a,b]=1000,[b,c]=2000,[c,a]=2000[a, b]=1000,[b, c]=2000,[c, a]=2000.

Official solution

Solution: Clearly, a,b,ca, b, c are all numbers of the form 2m5n2^{m} \cdot 5^{n}. Let a=2m15n1,b=2m25n2,c=2m35n3a=2^{m_{1}} \cdot 5^{n_{1}}, b=2^{m_{2}} \cdot 5^{n_{2}}, c=2^{m_{3}} \cdot 5^{n_{3}}. From [a,b]=1000=2353[a, b]=1000=2^{3} \cdot 5^{3}, we know max{m1,m2}=3,max{n1,n2}=3\max \left\{m_{1}, m_{2}\right\}=3, \max \left\{n_{1}, n_{2}\right\}=3. Similarly, max{m2,m3}=\max \left\{m_{2}, m_{3}\right\}= 4,max{n2,n3}=3,max{m1,m3}=4,max{n1,n3}=34, \max \left\{n_{2}, n_{3}\right\}=3, \max \left\{m_{1}, m_{3}\right\}=4, \max \left\{n_{1}, n_{3}\right\}=3.

Therefore, m3m_{3} should be 4, and m1,m2m_{1}, m_{2} must include one 3, and the other can be any of 0,1,20,1,2 or 3, so there are C41+C411=7C_{4}^{1}+C_{4}^{1}-1=7 ways to choose m1,m2m_{1}, m_{2}. Also, n1,n2,n3n_{1}, n_{2}, n_{3} must include two 3s, and the other can be 0,1,20,1,2 or 3, so there are C32+4=10C_{3}^{2}+4=10 ways to choose n1,n2,n3n_{1}, n_{2}, n_{3}. Therefore, the different ways to choose mi,ni(i=1,2,3)m_{i}, n_{i}(i=1,2,3) are 7×10=707 \times 10=70, meaning there are 70 triples.

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