Difference between revisions of "2021 AIME I Problems/Problem 14"
MRENTHUSIASM (talk | contribs) m (→Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)) |
MRENTHUSIASM (talk | contribs) m (→Video Solution) |
||
Line 108: | Line 108: | ||
==Video Solution== | ==Video Solution== | ||
https://youtu.be/q0zUFAyGN4s ~MathProblemSolvingSkills.com | https://youtu.be/q0zUFAyGN4s ~MathProblemSolvingSkills.com | ||
− | |||
− | |||
==See Also== | ==See Also== |
Revision as of 02:45, 6 August 2022
Contents
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
. Find the sum of the prime factors in the prime factorization of
.
Solution 1
We first claim that must be divisible by
. Since
is divisible by
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
, then
, so
must be divisible by
.
By similar reasoning, must be divisible by
, by considering
.
We next claim that must be divisible by
and
. Consider the case
. Then
, so
is divisible by
if and only if
is divisible by
.
Lastly, we claim that if , then
is divisible by
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
, so
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
, 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 (Along the Lines of Solution 1)
only needs to satisfy
and
for all
. Let's work on the first requirement (mod 43) first. All
works for
. If
, let
's prime factorization be
. The following three statements are the same:
- For all
, we have
.
- For all
and prime
, we have
.
- For all prime
, we have
.
We can show this by casework on :
- For
, no matter what
is, it is true that
- For all
, it is true that
One can either use brute force or Dirichlet's Theorem to show such
exists. Therefore,
.
- For all
, it is true that
According to Fermat's Little Theorem,
is sufficient. To show it's necessary we just need to show
has a prime primitive root. This can be done either by brute force or as follows.
is prime and it must have a primitive root
that's coprime to
. All numbers of the form
are also primitive roots of
. According to Dirichlet's Theorem there must be primes among them.
Similar arguments for modulo lead to
and
. Therefore, we get
. Following the last paragraph of Solution 1 gives the answer
.
~Mryang6859 (Solution)
~MRENTHUSIASM (Reformatting)
Solution 3 (Casework)
We perform casework on
For all positive integers
we have
is a prime number.
For all prime numbers
note that
by geometric series.
Recall that
Applying the Chinese Remainder Theorem, we get the following system of congruences:
We perform casework on
We need
If
then this congruence is true for all positive integers
If
then this congruence becomes
By Fermat's Little Theorem, we obtain
We need
to contain more factors of
than
does. More generally, for all positive integers
if
then
Let
for some positive integer
such that
We substitute this into
and apply the Binomial Theorem:
from which
we find that
and
For
we find that
and
by a similar argument.
Together, we conclude that
is the least such positive integer
for this case.
is a composite number.
Let
be the prime factorization of
Note that
is a multiplicative function:
as this product of geometric series spans all positive divisors of
At
it follows that
Finally, the least such positive integer for all cases is
so the sum of its prime factors is
~MRENTHUSIASM (inspired by Math Jams's 2021 AIME I Discussion)
Solution 4 (Cheap)
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
From here, follow solution 1 to get the final answer
.
-PureSwag
Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)
It says the problem implies that it works for all positive integers , we basically know that If
, then from "USEMO 2019 Problem 4", if
, then
From here we can just let
or be a power of
which we can do
which is a geometric series. We can plug in
like in Solution 4 and use CRT. We have the prime factorization
. We use CRT to find that
We see that this is just FLT which is
we see that all multiples of
will work for first and
for the second. We can figure out that it is just
which when we add up we get that it's just the sum of the prime factors of
which you can just look at Solution 1 to find out the sum of the prime factors and get the answer
.
Video Solution
https://youtu.be/q0zUFAyGN4s ~MathProblemSolvingSkills.com
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.