Difference between revisions of "2021 AIME I Problems/Problem 14"
Scrabbler94 (talk | contribs) (add a solution) |
Scrabbler94 (talk | contribs) |
||
Line 11: | Line 11: | ||
We next claim that <math>n</math> must be divisible by 43 and 47. Consider the case <math>a=2022</math>. Then <math>\sigma(a^n) \equiv n \pmod{2021}</math>, so <math>\sigma(2022^n)-1</math> is divisible by 2021 if and only if <math>n</math> is divisible by 2021. | We next claim that <math>n</math> must be divisible by 43 and 47. Consider the case <math>a=2022</math>. Then <math>\sigma(a^n) \equiv n \pmod{2021}</math>, so <math>\sigma(2022^n)-1</math> is divisible by 2021 if and only if <math>n</math> is divisible by 2021. | ||
− | Lastly, we claim that if <math>n = \text{lcm}(42, 46, 43, 47)</math>, then <math>\sigma(a^n) - 1</math> is divisible by 2021 for all positive integers <math>a</math>. The claim is trivially true for <math>a=1</math> so suppose <math>a>1</math>. Let <math>a = p_1^{e_1}\ldots p_k^{e_k}</math> be the prime factorization of <math>a</math>. Since <math>\sigma</math> is multiplicative, we have | + | Lastly, we claim that if <math>n = \text{lcm}(42, 46, 43, 47)</math>, then <math>\sigma(a^n) - 1</math> is divisible by 2021 for all positive integers <math>a</math>. The claim is trivially true for <math>a=1</math> so suppose <math>a>1</math>. Let <math>a = p_1^{e_1}\ldots p_k^{e_k}</math> be the prime factorization of <math>a</math>. Since <math>\sigma</math> is [[multiplicative function|multiplicative]], we have |
<cmath>\sigma(a^n) - 1 = \prod_{i=1}^k \sigma(p_i^{e_in}) - 1.</cmath> | <cmath>\sigma(a^n) - 1 = \prod_{i=1}^k \sigma(p_i^{e_in}) - 1.</cmath> | ||
We can show that <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math> for all primes <math>p_i</math> and integers <math>e_i \ge 1</math>, where | We can show that <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math> for all primes <math>p_i</math> and integers <math>e_i \ge 1</math>, where | ||
Line 17: | Line 17: | ||
where each expression in parentheses contains <math>n</math> terms. It is easy to verify that if <math>p_i = 43</math> or <math>p_i = 47</math> then <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math> for this choice of <math>n</math>, so suppose <math>p_i \not\equiv 0 \pmod{43}</math> and <math>p_i \not\equiv 0 \pmod{47}</math>. Each expression in parentheses equals <math>\frac{p_i^n - 1}{p_i - 1}</math> multiplied by some power of <math>p_i</math>. If <math>p_i \neq 1 \pmod{43}</math>, then FLT implies <math>p_i^n - 1 \equiv 0 \pmod{43}</math>, and if <math>p_i \equiv 1 \pmod{43}</math>, then <math>p_i + p_i^2 + \ldots + p_i^n \equiv 1 + 1 + \ldots + 1 \equiv 0 \pmod{43}</math> (since <math>n</math> is also a multiple of 43, by definition). Similarly, we can show <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{47}</math>, and a simple [[Chinese Remainder Theorem|CRT]] argument shows <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math>. Then <math>\sigma(a^n) \equiv 1^k \equiv 1 \pmod{2021}</math>. | where each expression in parentheses contains <math>n</math> terms. It is easy to verify that if <math>p_i = 43</math> or <math>p_i = 47</math> then <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math> for this choice of <math>n</math>, so suppose <math>p_i \not\equiv 0 \pmod{43}</math> and <math>p_i \not\equiv 0 \pmod{47}</math>. Each expression in parentheses equals <math>\frac{p_i^n - 1}{p_i - 1}</math> multiplied by some power of <math>p_i</math>. If <math>p_i \neq 1 \pmod{43}</math>, then FLT implies <math>p_i^n - 1 \equiv 0 \pmod{43}</math>, and if <math>p_i \equiv 1 \pmod{43}</math>, then <math>p_i + p_i^2 + \ldots + p_i^n \equiv 1 + 1 + \ldots + 1 \equiv 0 \pmod{43}</math> (since <math>n</math> is also a multiple of 43, by definition). Similarly, we can show <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{47}</math>, and a simple [[Chinese Remainder Theorem|CRT]] argument shows <math>\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}</math>. Then <math>\sigma(a^n) \equiv 1^k \equiv 1 \pmod{2021}</math>. | ||
− | Then the prime factors of <math>n</math> are <math>2</math>, <math>3</math>, <math>7</math>, <math>23</math>, <math>43</math>, and <math>47</math>, and the answer is <math>2+3+7+23+43+47 = \boxed{125}</math>. | + | Then the prime factors of <math>n</math> are <math>2</math>, <math>3</math>, <math>7</math>, <math>23</math>, <math>43</math>, and <math>47</math>, and the answer is <math>2+3+7+23+43+47 = \boxed{125}</math>. ~scrabbler94 |
==See also== | ==See also== | ||
{{AIME box|year=2021|n=I|num-b=13|num-a=15}} | {{AIME box|year=2021|n=I|num-b=13|num-a=15}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 21:23, 11 March 2021
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
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.