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"

(→‎Solution)
(→‎Solution 2 (cheap and not very reliable))
Line 20: Line 20:
  
 
==Solution 2 (cheap and not very reliable)==
 
==Solution 2 (cheap and not very reliable)==
−
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>\lcm{42, 43, 46, 47}.</math> From here, follow solution 1 to get the final answer.
+
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
 
-PureSwag

Revision as of 09:08, 12 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$. What is 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

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=149214"