2023 AMC 12A Problems/Problem 22
Contents
Problem
Let be the unique function defined on the positive integers such that for all positive integers . What is ?
Solution 1 (Very Thorough)
First, we note that , since the only divisor of is itself.
Then, let's look at for a prime. We see that
Nice.
Now consider , for . .
It can be (strongly) inductively shown that . Here's how.
We already showed works. Suppose it holds for , then
For , we have
, then using , we simplify to
.
Very nice! Now, we need to show that this function is multiplicative, i.e. for prime. It's pretty standard, let's go through it quickly. Using our formulas from earlier, we have
Great! We're almost done now. Let's actually plug in into the original formula. Let's use our formulas! We know
So plugging ALL that in, we have which, be my guest simplifying, is
~
Solution 2
First, change the problem into an easier form. So now we get Also, notice that both and are arithmetic functions. Applying Möbius inversion formula, we get So So the answer should be
~ZZZIIIVVV
Video Solution by MOP 2024
https://YouTube.com/watch?v=gdhVqdRhMsQ
~r00tsOfUnity
Video Solution by OmegaLearn
See also
2023 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 21 |
Followed by Problem 23 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.