2020 AMC 12A Problems/Problem 21
How many positive integers are there such that is a multiple of , and the least common multiple of and equals times the greatest common divisor of and
We set up the following equation as the problem states:
Breaking each number into its prime factorization, we see that the equation becomes
We can now determine the prime factorization of . We know that its prime factors belong to the set , as no factor of has in its prime factorization, nor anything greater. Next, we must find exactly how many different possibilities exist for each.
There can be anywhere between and 's and to 's. However, since is a multiple of , and we multiply the by , there can only be 's in 's prime factorization. Finally, there can either or 's.
Thus, we can multiply the total possibilities of 's factorization to determine the number of integers which satisfy the equation, giving us . ~ciceronii
Like the Solution 1, we starts from the equation:
Assume , with some integer . It follows that . It means that has a divisor . Since is a multiple of , has a divisor . Thus, . The equation can be changed as We can see that is also a multiple of , with a form of . Substituting it in the above equation, we have Similarly, is a multiple of , with a form of . We have The equation holds, if is a divisor of , which has divisors.
by Linty Huang
|2020 AMC 12A (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|