2022 AMC 12A Problem 23
Problem 23 of 25HarderNumber Theory
Let and be the unique relatively prime positive integers such that
Let denote the least common multiple of the numbers For how many integers with is
Answer choices
Show solution
Solution
is always divisible by so exactly when some prime divides both and the numerator (i.e. a prime cancels).
For a prime with maximal power only the terms with keep out of all others are divisible by So cancels iff
Applying this test recursively with gives for for and again for Finally, the ratios for are respectively. Thus cancellation occurs precisely for which is values.
Thus, the correct answer is D.