2004 IMO Shortlist Problems/N2
(Russia) The function from the set of positive integers to itself is defined by the equality
where denotes the greatest common divisor of and .
a) Prove that for every two relatively prime .
b) Prove that for each the equation has a solution.
c) Find all such that the equation has a unique solution.
This was also
Let be a divisor of . We note that for , if and only if is relatively prime to . It follows that each divisor of is found in the sum exactly times, where is defined as the number of natural numbers less than or equal to and relatively prime to (the Euler Totient Function). It follows that
In other words, is the convolution of the identity function and the function. Since these are both multiplicative functions, is also multiplicative, which is part (a) of the problem. For the next parts, we note that the equation is equivalent to the equation .
We now note that for a prime and a non-negative integer ,
Since is multiplicative, if is the prime factorization of , then
From this we can see that is always a solution to the equation , which solves part (b). Let this solution to the equation be the canonical solution. However, we also note that if is an odd postive integer, then is another solution to the equation. In particular, if has an odd prime factor , then is a solution distinct from the canonical solution. Thus if the only solution to the equation is canonical, then cannot have any odd divisors greater than 1, i.e., must be a power of 2.
We now claim that for , the equation has no non-canonical solutions.
Lemma. Let be odd primes, be positive integers. If
and are relatively prime positive integers, then is divisible by an odd prime.
Proof. We first note that , so , or . Thus must be divisible by some prime. But since , divides a product of odd numbers, so it cannot be divisible by 2. Hence is divisible by an odd prime. ∎
Now, suppose that for there exists some non-canonical solution to the equation. Since , the only value of which is a power of 2 and is a solution is the canonical solution. Thus , for some nonnegative integer and some odd integer . But by our lemma, , for some relatively prime and such that is odd. But since is an integer and there are no factors in the denominator common to the odd prime which divides , must be divisible by an odd prime, a contradiction. Thus the canonical solution to the equation is unique if and only if is a power of 2. Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.