Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎See also)
m
Line 3: Line 3:
  
 
==Solution 1==
 
==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 \neq 0,1 \pmod{43}</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\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> and <math>47</math>. 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 <math>2021</math> if and only if <math>n</math> is divisible by <math>2021</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
+
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</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>, 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</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
+
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
  
 
==Solution 2 (cheap and not very reliable)==
 
==Solution 2 (cheap and not very reliable)==

Revision as of 03:31, 31 July 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 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 \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\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$ 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$, 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

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\] 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{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 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.

Solution 4 (Along the line 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 3 statements are the same. \[\text{for all }a, \sigma(a^n)=\prod_{i=1}^k(1+p_i+\cdots+p_i^{ne_i})\equiv1\pmod{43}\] \[\text{for all }e>0\text{ and prime }p, 1+p+\cdots+p^{ne}\equiv1\pmod{43}\] \[\text{for all prime }p, p+p^2+\cdots+p^n \equiv 0 \pmod{43}\]


(1) For $p\equiv0\pmod{43}$, no matter $n$, it is true \[p+p^2+\cdots+p^n \equiv 0 \pmod{43}\]

(2) For all $p\equiv1\pmod{43}$, \[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.\]

(3) For all $p\not\equiv0,1\pmod{43}$, \[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 primes among them.

Similar arguments for (mod 47) lead to $46|n$ and $47|n$. Therefore \[n=\text{lcm}[42,43,46,47]\]

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&oldid=159312"