Difference between revisions of "2021 AIME I Problems/Problem 14"

Revision as of 11:24, 26 March 2021

Problem

For any positive integer $a, \sigma(a)$ denotes the sum of the positive integer divisors of $a$ . Let $n$ be the least positive integer such that $\sigma(a^n)-1$ is divisible by $2021$ for all positive integers $a$ . Find the sum of the prime factors in the prime factorization of $n$ .

Solution

We first claim that $n$ must be divisible by 42. Since $\sigma(a^n)-1$ is divisible by 2021 for all positive integers $a$ , we can first consider the special case where $a \neq 0,1 \pmod{43}$ .

Then $\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)$ . In order for this expression to be divisible by $2021=43\times 47$ , a necessary condition is $a^n - 1 \equiv 0 \pmod{43}$ . By Fermat's Little Theorem, $a^{42} \equiv 1 \pmod{43}$ . Moreover, if $a$ is a primitive root modulo 43, then $\text{ord}_{43}(a) = 42$ , so $n$ must be divisible by 42.

By similar reasoning, $n$ must be divisible by 46, by considering $a \neq 0,1 \pmod{47}$ .

We next claim that $n$ must be divisible by 43 and 47. Consider the case $a=2022$ . Then $\sigma(a^n) \equiv n \pmod{2021}$ , so $\sigma(2022^n)-1$ is divisible by 2021 if and only if $n$ is divisible by 2021.

Lastly, we claim that if $n = \text{lcm}(42, 46, 43, 47)$ , then $\sigma(a^n) - 1$ is divisible by 2021 for all positive integers $a$ . The claim is trivially true for $a=1$ so suppose $a>1$ . Let $a = p_1^{e_1}\ldots p_k^{e_k}$ be the prime factorization of $a$ . Since $\sigma$ is multiplicative, we have $\sigma(a^n) - 1 = \prod_{i=1}^k \sigma(p_i^{e_in}) - 1.$ We can show that $\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}$ for all primes $p_i$ and integers $e_i \ge 1$ , where $\sigma(p_i^{e_in}) = 1 + (p_i + p_i^2 + \ldots + p_i^n) + (p_i^{n+1} + \ldots + p_i^{2n}) + \ldots + (p_i^{n(e_i-1)+1} + \ldots + p_i^{e_in})$ where each expression in parentheses contains $n$ terms. It is easy to verify that if $p_i = 43$ or $p_i = 47$ then $\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}$ for this choice of $n$ , so suppose $p_i \not\equiv 0 \pmod{43}$ and $p_i \not\equiv 0 \pmod{47}$ . Each expression in parentheses equals $\frac{p_i^n - 1}{p_i - 1}$ multiplied by some power of $p_i$ . If $p_i \neq 1 \pmod{43}$ , then FLT implies $p_i^n - 1 \equiv 0 \pmod{43}$ , and if $p_i \equiv 1 \pmod{43}$ , then $p_i + p_i^2 + \ldots + p_i^n \equiv 1 + 1 + \ldots + 1 \equiv 0 \pmod{43}$ (since $n$ is also a multiple of 43, by definition). Similarly, we can show $\sigma(p_i^{e_in}) \equiv 1 \pmod{47}$ , and a simple CRT argument shows $\sigma(p_i^{e_in}) \equiv 1 \pmod{2021}$ . Then $\sigma(a^n) \equiv 1^k \equiv 1 \pmod{2021}$ .

Then the prime factors of $n$ are $2$ , $3$ , $7$ , $23$ , $43$ , and $47$ , and the answer is $2+3+7+23+43+47 = \boxed{125}$ . ~scrabbler94

Solution 2 (cheap and not very reliable)

Since the problem works for all positive integers $a$ , let's plug in $a=2$ and see what we get. Since $\sigma({2^n}) = 2^{n+1}-1,$ we have $2^{n+1} \equiv 2 \pmod{2021}.$ Simplifying using CRT and Fermat's Little Theorem, we get that $2^n \equiv 0 \pmod{42}$ and $2^n \equiv 0 \pmod{46}.$ Then, we can look at $a=2022$ just like in Solution 1 to find that $43$ and $47$ also divide $n$ . 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 $\text{lcm(42, 43, 46, 47)}.$ 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 $a$ , we basically know that If $p \equiv 1 \pmod q$ , than from "USEMO 2019 Problem 4 which was $p^n + p^{n-1} + ... + 1 \equiv 1$ (mod $q$ ) we have that $\frac{p^{en+1}-1}{p-1} \equiv p^{en} + p^{en-1} + \dots + 1 \equiv en + 1 \equiv 1 \pmod q,$ . From here we can just let $\sigma(2^n) or be a power of 2 which we can do$ \sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1$$ (Error compiling LaTeX. Unknown error_msg) which is a geo series. We can plug in $a=2^a$ like in Solution 2 and use CRT which when we prime factorize we get that $2021 = 43 \cdot 47$ which like everyone knows. We use CRT to find that $\begin{aligned} 2^{n} & \equiv 1 (\mod 43), \\ 2^{n} & \equiv 1 (\mod 47) . \end{aligned}$ . We see that this is just FLT which is $a^{p-1} \equiv 1 \pmod p$ we see all multiples of 42 will work for first and 46 for the second. We can figure out that it is just $\text{lcm}(43-1,47-1)\cdot43\cdot47$ 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 $p^n + p^{n-1} + ... + 1 \equiv 1$ which gave $p \equiv 1$ $q$ . Sorry if it's bad I need to do something else so I kind of rushed.

@@ Line 23: / Line 23: @@
 -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 <math>a</math>, we basically know that If <math>p \equiv 1 \pmod q</math>, than from "USEMO 2019 Problem 4 which was <math>p^n + p^{n-1} + ... + 1 \equiv 1</math> (mod <math>q</math>) we have that <cmath>\frac{p^{en+1}-1}{p-1} \equiv p^{en} + p^{en-1} + \dots + 1 \equiv en + 1 \equiv 1 \pmod q,</cmath>. From here we can just let <cmath>\sigma(2^n) or be a power of 2 which we can do </cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1<math></math> which is a geo series. We can plug in <math>a=2^a</math> like in Solution 2 and use CRT which when we prime factorize we get that <math>2021 = 43 \cdot 47</math> which like everyone knows. We use CRT to find that  $\begin{aligned} 2^{n} & \equiv 1 (\mod 43), \\ 2^{n} & \equiv 1 (\mod 47) . \end{aligned}$ . We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see all multiples of 42 will work for first and 46 for the second. We can figure out that it is just <math>\text{lcm}(43-1,47-1)\cdot43\cdot47</math> 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 <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.
 ==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

Page

Toolbox

Search