Maths Olympiad Prep

Library / /14 of 15

Number theory Difficulty 5.8 AIME, harder Prove it United States

Problem:
Let gcd mean the greatest common divisor of two numbers and lcm their least common multiple. Suppose the three numbers AA, BB, CC satisfy

gcd(A,B)=2,lcm(A,B)=60gcd(A,C)=3,lcm(A,C)=42 \begin{array}{ll} \operatorname{gcd}(A, B)=2, & \operatorname{lcm}(A, B)=60 \\ \operatorname{gcd}(A, C)=3, & \operatorname{lcm}(A, C)=42 \end{array}

Determine the three numbers.

Solution

Solution:
From the given information, AA must be a multiple of 22 and 33, and thus a multiple of LCM(2,3)=6\operatorname{LCM}(2,3)=6. It also must be a factor of 6060 and 4242, and thus a factor of GCD(60,42)=6\operatorname{GCD}(60,42)=6. The only possibility is A=6A=6.

Since LCM(A,B)\operatorname{LCM}(A, B) is divisible by 55 but AA is not, BB must be divisible by 55. Similarly, since LCM(A,B)\operatorname{LCM}(A, B) is divisible by 22=42^{2}=4 but AA is not, BB must also be a multiple of 44 and thus a multiple of 2020. BB cannot be 6060 or we would have GCD(A,B)=6\operatorname{GCD}(A, B)=6, thus B=20B=20.

Finally, since LCM(A,C)\operatorname{LCM}(A, C) is a multiple of 77 but AA is not, CC must be divisible by 77. Also, CC is divisible by 33 since GCD(A,C)=3\operatorname{GCD}(A, C)=3. Thus, CC is a multiple of 2121, and we cannot have C=42C=42 or else GCD(A,C)\operatorname{GCD}(A, C) would be 66. Thus, C=21C=21, giving the solution A=6A=6, B=20B=20, C=21C=21.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.