Difference between revisions of "2021 AIME I Problems/Problem 14"
(Added in "Category".)
|Line 20:||Line 20:|
Revision as of 01:34, 12 March 2021
For any positive integer denotes the sum of the positive integer divisors of . Let be the least positive integer such that is divisible by for all positive integers . What is the sum of the prime factors in the prime factorization of ?
We first claim that must be divisible by 42. Since is divisible by 2021 for all positive integers , we can first consider the special case where .
Then . In order for this expression to be divisible by , a necessary condition is . By Fermat's Little Theorem, . Moreover, if is a primitive root modulo 43, then , so must be divisible by 42.
By similar reasoning, must be divisible by 46, by considering .
We next claim that must be divisible by 43 and 47. Consider the case . Then , so is divisible by 2021 if and only if is divisible by 2021.
Lastly, we claim that if , then is divisible by 2021 for all positive integers . The claim is trivially true for so suppose . Let be the prime factorization of . Since is multiplicative, we have We can show that for all primes and integers , where where each expression in parentheses contains terms. It is easy to verify that if or then for this choice of , so suppose and . Each expression in parentheses equals multiplied by some power of . If , then FLT implies , and if , then (since is also a multiple of 43, by definition). Similarly, we can show , and a simple CRT argument shows . Then .
Then the prime factors of are , , , , , and , and the answer is . ~scrabbler94
|2021 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|