Difference between revisions of "2021 AIME I Problems/Problem 14"
MRENTHUSIASM (talk | contribs) (→Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)) |
m (→Remark (Dirichlet's Theorem)) |
||
(5 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, such <math>a</math> always exists. | + | 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 01: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
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.