Difference between revisions of "2021 AIME I Problems/Problem 14"
MRENTHUSIASM (talk | contribs) m (→Solution 1) |
m (→Remark (Dirichlet's Theorem)) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
==Solution 1== | ==Solution 1== | ||
− | We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem (Refer to the <b>Remark</b> | + | We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem (Refer to the <b>Remark</b> section.), such <math>a</math> always exists. |
Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>. | Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>. | ||
Line 10: | Line 10: | ||
We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>. | We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>. | ||
+ | |||
+ | Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}(a)+v_{43}{(a-1)}+v_{43}{(n)}-v_{43}{(a-1)} \geq 1,</math> which simplifies to <math>v_{43}(n) \geq 1,</math> which implies the desired result. | ||
Similarly, <math>n</math> is a multiple of <math>47</math>. | Similarly, <math>n</math> is a multiple of <math>47</math>. | ||
Line 111: | Line 113: | ||
==Remark (Dirichlet's Theorem)== | ==Remark (Dirichlet's Theorem)== | ||
− | All solutions require Dirichlet's Theorem, which states that for any coprime integers <math>k</math> and <math>r</math>, there | + | All solutions require Dirichlet's Theorem, which states that for any coprime positive integers <math>k</math> and <math>r</math>, there are infinitely many primes <math>p</math> congruent to <math>r\pmod{k}</math>. |
==Video Solution== | ==Video Solution== |
Latest revision as of 02:28, 13 November 2023
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
is prime and
. By Dirichlet's Theorem (Refer to the Remark section.), such
always exists.
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
. By Dirichlet, let
be a prime that is congruent to
. Then
, so since
is divisible by
,
is a multiple of
.
Alternatively, since must be divisible by
by LTE, we have
which simplifies to
which implies the desired result.
Similarly, is a multiple of
.
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, Revised by wzs26843545602
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 infinitely many 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
being a
prime and a
prime, 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)
Warning: This solution doesn't explain why .
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
.
Remark (Dirichlet's Theorem)
All solutions require Dirichlet's Theorem, which states that for any coprime positive integers and
, there are infinitely many primes
congruent to
.
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.