Difference between revisions of "2021 AIME I Problems/Problem 14"
Sugar rush (talk | contribs) (Added in "Category".) |
(→Solution) |
||
Line 18: | Line 18: | ||
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</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 (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. | ||
+ | |||
+ | -PureSwag | ||
+ | |||
==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}} |
Revision as of 10:07, 12 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
Solution 2 (cheap and not very reliable)
Since the problem works for all positive integers , let's plug in and see what we get. Since we have Simplifying using CRT and [[Fermat's Little Theorem[[, we get that and Then, we can look at just like in Solution 1 to find that and also divide . 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 $\lcm{42, 43, 46, 47}.$ (Error compiling LaTeX. ! Undefined control sequence.) 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.