2021 AIME I Problems/Problem 14
Problem
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
?
Solution
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
Solution 2 (cheap and not very reliable)
Since the problem works for all positive integers , let's plug in
and see what we get. Since
we have
Simplifying using CRT and [[Fermat's Little Theorem[[, we get that
and
Then, we can look at
just like in Solution 1 to find that
and
also divide
. There don't seem to be any other odd "numbers" to check, so we can hopefully assume that the answer is the sum of the prime factors of $\lcm{42, 43, 46, 47}.$ (Error compiling LaTeX. Unknown error_msg) From here, follow solution 1 to get the final answer.
-PureSwag
See also
2021 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.