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

Latest revision as of 01:28, 13 November 2023

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 1

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$ is prime and $a \neq 0,1 \pmod{43}$ . By Dirichlet's Theorem (Refer to the Remark section.), such $a$ always exists.

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\cdot 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 \not\equiv 0,1 \pmod{47}$ .

We next claim that $n$ must be divisible by $43$ . By Dirichlet, let $a$ be a prime that is congruent to $1 \pmod{43}$ . Then $\sigma(a^n) \equiv n+1 \pmod{43}$ , so since $\sigma(a^n)-1$ is divisible by $43$ , $n$ is a multiple of $43$ .

Alternatively, since $\left(\frac{a(a^n - 1^n)}{a-1}\right)$ must be divisible by $43,$ by LTE, we have $v_{43}(a)+v_{43}{(a-1)}+v_{43}{(n)}-v_{43}{(a-1)} \geq 1,$ which simplifies to $v_{43}(n) \geq 1,$ which implies the desired result.

Similarly, $n$ is a multiple of $47$ .

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(n)$ 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$ , so $\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 \not\equiv 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, Revised by wzs26843545602

Solution 2 (Along the Lines of Solution 1)

$n$ only needs to satisfy $\sigma(a^n)\equiv 1 \pmod{43}$ and $\sigma(a^n)\equiv 1 \pmod{47}$ for all $a$ . Let's work on the first requirement (mod 43) first. All $n$ works for $a=1$ . If $a>1$ , let $a$ 's prime factorization be $a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ . The following three statements are the same:

For all $a$ , we have $\sigma(a^n)=\prod_{i=1}^k(1+p_i+\cdots+p_i^{ne_i})\equiv1\pmod{43}$ .

For all $e>0$ and prime $p$ , we have $1+p+\cdots+p^{ne}\equiv1\pmod{43}$ .

For all prime $p$ , we have $p+p^2+\cdots+p^n \equiv 0 \pmod{43}$ .

We can show this by casework on $p$ :

For $p\equiv0\pmod{43}$ , no matter what $n$ is, it is true that $p+p^2+\cdots+p^n \equiv 0 \pmod{43}.$

For all $p\equiv1\pmod{43}$ , it is true that $p+p^2+\cdots+p^n \equiv n \equiv 0 \pmod{43}.$ One can either use brute force or Dirichlet's Theorem to show such $p$ exists. Therefore, $43|n$ .

For all $p\not\equiv0,1\pmod{43}$ , it is true that $p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}.$ According to Fermat's Little Theorem, $42|n$ 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 $t\neq 1$ that's coprime to $43$ . All numbers of the form $43k+t$ are also primitive roots of $43$ . According to Dirichlet's Theorem there must be infinitely many primes among them.

Similar arguments for modulo $47$ lead to $46|n$ and $47|n$ . Therefore, we get $n=\operatorname{lcm}[42,43,46,47]$ . Following the last paragraph of Solution 1 gives the answer $\boxed{125}$ .

~Mryang6859 (Solution)

~MRENTHUSIASM (Reformatting)

Solution 3 (Casework)

We perform casework on $a:$

$a=1.$
For all positive integers $n,$ we have $\sigma\left(a^n\right)-1=0.$
is a prime number.
For all prime numbers $p,$ note that $\sigma\left(p^n\right)-1=\left(\sum_{i=0}^{n}p^i\right)-1=\sum_{i=1}^{n}p^i=\frac{p^{n+1}-p}{p-1}=\frac{p\left(p^n-1\right)}{p-1}$ by geometric series.
Recall that $2021=43\cdot47.$ Applying the Chinese Remainder Theorem, we get the following system of congruences: $\begin{align*} \frac{p\left(p^n-1\right)}{p-1}&\equiv0\pmod{43}, &(1)\\ \frac{p\left(p^n-1\right)}{p-1}&\equiv0\pmod{47}. &(2) \end{align*}$ We perform casework on $(1):$
1. $p-1\not\equiv0\pmod{43}.$
  We need $p\left(p^n-1\right)\equiv0\pmod{43}.$
  If $p=43,$ then this congruence is true for all positive integers $n.$
  If $p\neq43,$ then this congruence becomes $p^n-1\equiv0\pmod{43}.$ By Fermat's Little Theorem, we obtain $n\equiv0\pmod{42}.$
2. $p-1\equiv0\pmod{43}.$
  We need $p^n-1$ to contain more factors of $43$ than $p-1$ does. More generally, for all positive integers $k,$ if $p-1\equiv0 \ \left(\operatorname{mod} \ 43^k\right),$ then $p^n-1\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right).$
  Let $p=43^km+1$ for some positive integer $m$ such that $m\not\equiv0\pmod{43}.$ We substitute this into $p^n-1\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right)$ and apply the Binomial Theorem: $\begin{align*} \left(43^km+1\right)^n-1&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\ \Biggl[\binom{n}{0}\left(43^km\right)^0+\binom{n}{1}\left(43^km\right)^1+\phantom{ }\underbrace{\binom{n}{2}\left(43^km\right)^2+\cdots+\binom{n}{n}\left(43^km\right)^n}_{0 \ \left(\operatorname{mod} \ 43^{k+1}\right)}\phantom{ }\Biggr]-1 &\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\ \left[1+43^kmn\right]-1&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\ 43^kmn&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right), \end{align*}$ from which $n\equiv0\pmod{43}.$
For we find that and
For $(2),$ we find that $n\equiv0\pmod{46}$ and $n\equiv0\pmod{47}$ by a similar argument.
Together, we conclude that $n=\operatorname{lcm}(42,43,46,47)$ is the least such positive integer $n$ for this case.

$a$ is a composite number.
Let $a=\prod_{i=1}^{u}p_i^{e_i}$ be the prime factorization of $a.$ Note that $\sigma(a)$ is a multiplicative function: $\sigma(a)=\sigma\left(\prod_{i=1}^{u}p_i^{e_i}\right)=\prod_{i=1}^{u}\sigma\left(p_i^{e_i}\right)=\prod_{i=1}^{u}\left(\sum_{j=0}^{e_i}p_i^j\right),$ as this product of geometric series spans all positive divisors of $a.$
At $n=\operatorname{lcm}(42,43,46,47),$ it follows that $\begin{align*} \sigma\left(a^n\right)-1&=\left(\prod_{i=1}^{u}\sigma\left(p_i^{e_in}\right)\right)-1 \\ &\equiv\left(\prod_{i=1}^{u}1\right)-1 &&\pmod{2021} \\ &\equiv0 &&\pmod{2021}. \end{align*}$

Finally, the least such positive integer $n$ for all cases is $\begin{align*} n&=\operatorname{lcm}(42,43,46,47) \\ &=\operatorname{lcm}(2\cdot3\cdot7,43,2\cdot23,47) \\ &=2\cdot3\cdot7\cdot23\cdot43\cdot47, \end{align*}$ so the sum of its prime factors is $2+3+7+23+43+47=\boxed{125}.$

~MRENTHUSIASM (inspired by Math Jams's 2021 AIME I Discussion)

Solution 4 (Cheap)

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 $n \equiv 0 \pmod{42}$ and $n \equiv 0 \pmod{46}.$ Then, we can look at $a$ being a $1\pmod{43}$ prime and a $1\pmod{47}$ prime, 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 $\boxed{125}$ .

~PureSwag

Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)

Warning: This solution doesn't explain why $43*47\mid n$ .

It says the problem implies that it works for all positive integers $a$ , we basically know that If $p \equiv 1 \pmod q$ , then from "USEMO 2019 Problem 4", if $p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}$ , then $\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 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,$ which is a geometric series. We can plug in $a=2$ like in Solution 4 and use CRT. We have the prime factorization $2021 = 43 \cdot 47$ . 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 $a^{p-1} \equiv 1 \pmod p$ we see that 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 $\text{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 $\boxed{125}$ .

Remark (Dirichlet's Theorem)

All solutions require Dirichlet's Theorem, which states that for any coprime positive integers $k$ and $r$ , there are infinitely many primes $p$ congruent to $r\pmod{k}$ .

Video Solution

https://youtu.be/q0zUFAyGN4s ~MathProblemSolvingSkills.com

@@ Line 2: / Line 2: @@
 For any positive integer <math>a, \sigma(a)</math> denotes the sum of the positive integer divisors of <math>a</math>. Let <math>n</math> be the least positive integer such that <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. Find the sum of the prime factors in the prime factorization of <math>n</math>.
-==Solution==
+==Solution 1==
-We first claim that <math>n</math> must be divisible by 42. Since <math>\sigma(a^n)-1</math> is divisible by 2021 for all positive integers <math>a</math>, we can first consider the special case where <math>a \neq 0,1 \pmod{43}</math>.
+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\times 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 43, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by 42.
+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>.
-By similar reasoning, <math>n</math> must be divisible by 46, by considering <math>a \neq 0,1 \pmod{47}</math>.
+By similar reasoning, <math>n</math> must be divisible by <math>46</math>, by considering <math>a \not\equiv 0,1 \pmod{47}</math>.
-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 <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>.
-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
+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>.
+Lastly, we claim that if <math>n = \text{lcm}(42, 46, 43, 47)</math>, then <math>\sigma(a^n) - 1</math> is divisible by <math>2021</math> 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(n)</math> is [[multiplicative function|multiplicative]], we have
 <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>, so
-<cmath>\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})</cmath>
+<cmath>\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}),</cmath>
-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 \not\equiv 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 <math>43</math>, 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,3,7,23,43,</math> and <math>47,</math> and the answer is <math>2+3+7+23+43+47 = \boxed{125}</math>.
+~scrabbler94, Revised by wzs26843545602
-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
+==Solution 2 (Along the Lines of Solution 1)==
+<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 three statements are the same:
+<ol style="margin-left: 1.5em;">
+  <li>For all <math>a</math>, we have <math>\sigma(a^n)=\prod_{i=1}^k(1+p_i+\cdots+p_i^{ne_i})\equiv1\pmod{43}</math>.</li><p>
+  <li>For all <math>e>0</math> and prime <math>p</math>, we have <math>1+p+\cdots+p^{ne}\equiv1\pmod{43}</math>.</li><p>
+  <li>For all prime <math>p</math>, we have <math>p+p^2+\cdots+p^n \equiv 0 \pmod{43}</math>.</li><p>
+</ol>
+We can show this by casework on <math>p</math>:
+<ol style="margin-left: 1.5em;">
+  <li>For <math>p\equiv0\pmod{43}</math>, no matter what <math>n</math> is, it is true that <cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43}.</cmath></li><p>
+  <li>For all <math>p\equiv1\pmod{43}</math>, it is true that <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, <math>43|n</math>.</li><p>
+  <li>For all <math>p\not\equiv0,1\pmod{43}</math>, it is true that
+<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 <math>43</math> has a prime primitive root. This can be done either by brute force or as follows. <math>43</math> is prime and it must have a primitive root <math>t\neq 1</math> that's coprime to <math>43</math>. All numbers of the form <math>43k+t</math> are also primitive roots of <math>43</math>. According to Dirichlet's Theorem there must be infinitely many primes among them.</li><p>
+</ol>
+Similar arguments for modulo <math>47</math> lead to <math>46|n</math> and <math>47|n</math>. Therefore, we get <math>n=\operatorname{lcm}[42,43,46,47]</math>. Following the last paragraph of Solution 1 gives the answer <math>\boxed{125}</math>.
-==Solution 2 (cheap and not very reliable)==
+~Mryang6859 (Solution)
-Since the problem works for all positive integers <math>a</math>, let's plug in <math>a=2</math> and see what we get. Since <math>\sigma({2^n}) = 2^{n+1}-1,</math> we have <math>2^{n+1} \equiv 2 \pmod{2021}.</math> Simplifying using CRT and [[Fermat's Little Theorem]], we get that <math>2^n \equiv 0 \pmod{42}</math> and <math>2^n \equiv 0 \pmod{46}.</math> Then, we can look at <math>a=2022</math> just like in Solution 1 to find that <math>43</math> and <math>47</math> also divide <math>n</math>. 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 <math>\text{lcm(42, 43, 46, 47)}.</math> From here, follow solution 1 to get the final answer.
--PureSwag
+~MRENTHUSIASM (Reformatting)
-==Solution 3 (Kind of similar to Sol 2 and kind of what cosmicgenius said)==
+==Solution 3 (Casework)==
-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 <math>\sigma(2^n)</math> 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</cmath> 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{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}. 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.
+We perform casework on <math>a:</math>
+<ol style="margin-left: 1.5em;">
+  <li><math>a=1.</math> <p>
+For all positive integers <math>n,</math> we have <math>\sigma\left(a^n\right)-1=0.</math>
+</li>
+  <li><math>a</math> is a prime number. <p>
+For all prime numbers <math>p,</math> note that
+<cmath>\sigma\left(p^n\right)-1=\left(\sum_{i=0}^{n}p^i\right)-1=\sum_{i=1}^{n}p^i=\frac{p^{n+1}-p}{p-1}=\frac{p\left(p^n-1\right)}{p-1}</cmath>
+by geometric series. <p>
+Recall that <math>2021=43\cdot47.</math> Applying the Chinese Remainder Theorem, we get the following system of congruences:
+<cmath>\begin{align*}
+\frac{p\left(p^n-1\right)}{p-1}&\equiv0\pmod{43}, &(1)\\
+\frac{p\left(p^n-1\right)}{p-1}&\equiv0\pmod{47}. &(2)
+\end{align*}</cmath>
+We perform casework on <math>(1):</math>
+<ol style="margin-left: 1.5em;" type="A">
+  <li><math>p-1\not\equiv0\pmod{43}.</math> <p>
+We need <math>p\left(p^n-1\right)\equiv0\pmod{43}.</math> <p>
+If <math>p=43,</math> then this congruence is true for all positive integers <math>n.</math> <p>
+If <math>p\neq43,</math> then this congruence becomes <math>p^n-1\equiv0\pmod{43}.</math> By Fermat's Little Theorem, we obtain <math>n\equiv0\pmod{42}.</math></li>
+  <li><math>p-1\equiv0\pmod{43}.</math> <p>
+We need <math>p^n-1</math> to contain more factors of <math>43</math> than <math>p-1</math> does. More generally, for all positive integers <math>k,</math> if <math>p-1\equiv0 \ \left(\operatorname{mod} \ 43^k\right),</math> then <math>p^n-1\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right).</math> <p>
+Let <math>p=43^km+1</math> for some positive integer <math>m</math> such that <math>m\not\equiv0\pmod{43}.</math> We substitute this into <math>p^n-1\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right)</math> and apply the Binomial Theorem:
+<cmath>\begin{align*}
+\left(43^km+1\right)^n-1&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\
+\Biggl[\binom{n}{0}\left(43^km\right)^0+\binom{n}{1}\left(43^km\right)^1+\phantom{ }\underbrace{\binom{n}{2}\left(43^km\right)^2+\cdots+\binom{n}{n}\left(43^km\right)^n}_{0 \ \left(\operatorname{mod} \ 43^{k+1}\right)}\phantom{ }\Biggr]-1 &\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\
+\left[1+43^kmn\right]-1&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right) \\
+^kmn&\equiv0 \ \left(\operatorname{mod} \ 43^{k+1}\right),
+\end{align*}</cmath>
+from which <math>n\equiv0\pmod{43}.</math>
+</li>
+</ol>
+For <math>(1),</math> we find that <math>n\equiv0\pmod{42}</math> and <math>n\equiv0\pmod{43}.</math> <p>
+For <math>(2),</math> we find that <math>n\equiv0\pmod{46}</math> and <math>n\equiv0\pmod{47}</math> by a similar argument. <p>
+Together, we conclude that <math>n=\operatorname{lcm}(42,43,46,47)</math> is the least such positive integer <math>n</math> for this case.
+</li><p>
+  <li><math>a</math> is a composite number. <p>
+Let <math>a=\prod_{i=1}^{u}p_i^{e_i}</math> be the prime factorization of <math>a.</math> Note that <math>\sigma(a)</math> is a multiplicative function: <cmath>\sigma(a)=\sigma\left(\prod_{i=1}^{u}p_i^{e_i}\right)=\prod_{i=1}^{u}\sigma\left(p_i^{e_i}\right)=\prod_{i=1}^{u}\left(\sum_{j=0}^{e_i}p_i^j\right),</cmath> as this product of geometric series spans all positive divisors of <math>a.</math> <p>
+At <math>n=\operatorname{lcm}(42,43,46,47),</math> it follows that
+<cmath>\begin{align*}
+\sigma\left(a^n\right)-1&=\left(\prod_{i=1}^{u}\sigma\left(p_i^{e_in}\right)\right)-1 \\
+&\equiv\left(\prod_{i=1}^{u}1\right)-1 &&\pmod{2021} \\
+&\equiv0 &&\pmod{2021}.
+\end{align*}</cmath>
+</li><p>
+</ol>
+Finally, the least such positive integer <math>n</math> for all cases is
+<cmath>\begin{align*}
+n&=\operatorname{lcm}(42,43,46,47) \\
+&=\operatorname{lcm}(2\cdot3\cdot7,43,2\cdot23,47) \\
+&=2\cdot3\cdot7\cdot23\cdot43\cdot47,
+\end{align*}</cmath>
+so the sum of its prime factors is <math>2+3+7+23+43+47=\boxed{125}.</math>
-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.
+~MRENTHUSIASM (inspired by Math Jams's <b>2021 AIME I Discussion</b>)
-==Solution 4 (Along the line of Solution 1)==
+==Solution 4 (Cheap)==
-<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.
+Since the problem works for all positive integers <math>a</math>, let's plug in <math>a=2</math> and see what we get. Since <math>\sigma({2^n}) = 2^{n+1}-1,</math> we have <math>2^{n+1} \equiv 2 \pmod{2021}.</math> Simplifying using CRT and [[Fermat's Little Theorem]], we get that <math>n \equiv 0 \pmod{42}</math> and <math>n \equiv 0 \pmod{46}.</math> Then, we can look at <math>a</math> being a <math>1\pmod{43}</math> prime and a <math>1\pmod{47}</math> prime, just like in Solution 1, to find that <math>43</math> and <math>47</math> also divide <math>n</math>. 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 <math>\text{lcm(42, 43, 46, 47)}.</math> From here, follow solution 1 to get the final answer <math>\boxed{125}</math>.
-<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>
+~PureSwag
-(1) For <math>p\equiv0\pmod{43}</math>, no matter <math>n</math>, it is true
+==Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)==
-<cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43}</cmath>
+Warning: This solution doesn't explain why <math>43*47\mid n</math>.
-(2) For all <math>p\equiv1\pmod{43}</math>,
+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>, then from "USEMO 2019 Problem 4", if <math>p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}</math>, then <cmath>\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 1 \equiv 1 \pmod{q}.</cmath> From here we can just let <math>\sigma(2^n)</math> or be a power of <math>2</math> which we can do <cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1,</cmath> which is a geometric series. We can plug in <math>a=2</math> like in Solution 4 and use CRT. We have the prime factorization <math>2021 = 43 \cdot 47</math>. We use CRT to find that <cmath>\begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}</cmath> We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see that all multiples of <math>42</math> will work for first and <math>46</math> 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 <math>\text{lcm}(42,43,46,47)</math> which you can just look at Solution 1 to find out the sum of the prime factors and get the answer <math>\boxed{125}</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>,
+==Remark (Dirichlet's Theorem)==
-<cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}</cmath>
+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>.
-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\neq 1</math> that's coprime to 43. 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) lead to <math>46|n</math> and <math>47|n</math>. Therefore
+==Video Solution==
-<cmath>n=\text{lcm}[42,43,46,47]</cmath>
+https://youtu.be/q0zUFAyGN4s   ~MathProblemSolvingSkills.com
-==See also==
+==See Also==
 {{AIME box|year=2021|n=I|num-b=13|num-a=15}}
 [[Category:Intermediate Number Theory Problems]]
 {{MAA Notice}}

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