2004 IMO Shortlist Problems/N2
Problem
(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
Solution
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
,
and
.
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.