2022 AMC 12A Problems/Problem 23
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 ?
We are given that Since we need
For all primes such that let be the largest power of that is a factor of
It is clear that so we test whether Note that We construct the following table for Note that:
- If the Sum column has only one term, then it is never congruent to modulo
- If and are positive integers such that then is a multiple of Therefore, for a specific case, if the sum is congruent to modulo for the smallest element in the interval of then it is also congruent to modulo for all other elements in the interval of
Together, there are such integers namely ~MRENTHUSIASM
We will use the following lemma to solve this problem.
Denote by the prime factorization of . For any , denote , where and are relatively prime. Then if and only if for any , is not a multiple of .
Now, we use the result above to solve this problem.
Following from this lemma, the list of with and is
Therefore, the answer is .
Note: Detailed analysis of this problem (particularly the motivation and the proof of the lemma above) can be found in my video solution below.
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution by Math-X (Smart and Simple)
|2022 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|