Skip to main content
OlympiadHQ

Browse · harp

Print

smc

number theory senior

Problem

Let be the unique function defined on the positive integers such that for all positive integers . What is ?
(A)
(B)
(C)
(D)
Solution
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
Final answer
B