Difference between revisions of "2021 AIME I Problems/Problem 14"
Pangpang80 (talk | contribs) (→Solution 3 (Kind of similar to Sol 2 and kind of what cosmicgenius said)) |
Mryang6859 (talk | contribs) |
||
Line 28: | Line 28: | ||
Remarks: This was kind of used in what cosmicgenius and Solution 2 said and what mathisawesome2169 said and It "Reminded me of 2019 USEMO Problem 4 when solving the <math>p^n + p^{n-1} + ... + 1 \equiv 1</math> which gave <math>p \equiv 1</math> <math>q</math>. Sorry if it's bad I need to do something else so I kind of rushed. | Remarks: This was kind of used in what cosmicgenius and Solution 2 said and what mathisawesome2169 said and It "Reminded me of 2019 USEMO Problem 4 when solving the <math>p^n + p^{n-1} + ... + 1 \equiv 1</math> which gave <math>p \equiv 1</math> <math>q</math>. Sorry if it's bad I need to do something else so I kind of rushed. | ||
+ | |||
+ | ==Solution 4== | ||
+ | <math>n</math> only needs to satisfy <math>\sigma(a^n)\equiv 1 \pmod{43}</math> and <math>\sigma(a^n)\equiv 1 \pmod{47}</math> for all <math>a</math>. Let's work on the first requirement (mod 43) first. All <math>n</math> works for <math>a=1</math>. If <math>a>1</math>, let <math>a</math>'s prime factorization be <math>a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}</math>. The following 3 statements are the same. | ||
+ | <cmath>\text{for all }a, \sigma(a^n)=\prod_{i=1}^k(1+p_i+\cdots+p_i^{ne_i})\equiv1\pmod{43}</cmath> | ||
+ | <cmath>\text{for all }e>0\text{ and prime }p, 1+p+\cdots+p^{ne}\equiv1\pmod{43}</cmath> | ||
+ | <cmath>\text{for all prime }p, p+p^2+\cdots+p^n \equiv 0 \pmod{43}</cmath> | ||
+ | |||
+ | |||
+ | (1) For <math>p\equiv0\pmod{43}</math>, no matter <math>n</math>, it is true | ||
+ | <cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43}</cmath> | ||
+ | |||
+ | (2) For all <math>p\equiv1\pmod{43}</math>, | ||
+ | <cmath>p+p^2+\cdots+p^n \equiv n \equiv 0 \pmod{43}</cmath> | ||
+ | One can either use brute force or Dirichlet's Theorem to show such <math>p</math> exists. Therefore | ||
+ | <cmath>43|n.</cmath> | ||
+ | |||
+ | (3) For all <math>p\not\equiv0,1\pmod{43}</math>, | ||
+ | <cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}</cmath> | ||
+ | According to Fermat's Little Theorem, <math>42|n</math> is sufficient. To show it's necessary we just need to show 43 has a prime primitive root. This can be done either by brute force or as follows. 43 is prime and it must have a primitive root <math>t</math>. And all numbers of the form <math>43k+t</math> are also primitive roots of 43. According to Dirichlet's Theorem there must be primes among them. | ||
+ | |||
+ | Similar arguments for (mod 47) leads to <math>46|n</math> and <math>47|n</math>. Therefore | ||
+ | <cmath>n=\text{lcm}[42,43,46,47]</cmath> | ||
==See also== | ==See also== |
Revision as of 22:28, 7 April 2021
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
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 From here, follow solution 1 to get the final answer.
-PureSwag
Solution 3 (Kind of similar to Sol 2 and kind of what cosmicgenius said)
It says the problem implies that it works for all positive integers , we basically know that If , than from "USEMO 2019 Problem 4 which was (mod ) we have that . From here we can just let or be a power of 2 which we can do which is a geo series. We can plug in like in Solution 2 and use CRT which when we prime factorize we get that which like everyone knows. We use CRT to find that \begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}. We see that this is just FLT which is we see all multiples of 42 will work for first and 46 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 lcm(42,43,46,47) which you can just look at Solution 1 to find out the sum of the prime factors and get the answer.
Remarks: This was kind of used in what cosmicgenius and Solution 2 said and what mathisawesome2169 said and It "Reminded me of 2019 USEMO Problem 4 when solving the which gave . Sorry if it's bad I need to do something else so I kind of rushed.
Solution 4
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 3 statements are the same.
(1) For , no matter , it is true
(2) For all , One can either use brute force or Dirichlet's Theorem to show such exists. Therefore
(3) For all , According to Fermat's Little Theorem, is sufficient. To show it's necessary we just need to show 43 has a prime primitive root. This can be done either by brute force or as follows. 43 is prime and it must have a primitive root . And all numbers of the form are also primitive roots of 43. According to Dirichlet's Theorem there must be primes among them.
Similar arguments for (mod 47) leads to and . Therefore
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.