2004 IMO Shortlist Problems/N2

Problem

(Russia) The function $\displaystyle \psi$ from the set $\mathbf{N}$ of positive integers to itself is defined by the equality

$\psi(n) = \sum_{k=1}^{n}(k,n), \qquad n \in \mathbf{N}$ ,

where $\displaystyle (k,n)$ denotes the greatest common divisor of $\displaystyle k$ and $\displaystyle n$ .

a) Prove that $\displaystyle \psi(mn) = \psi(m)\psi(n)$ for every two relatively prime $m,n \in \mathbf{N}$ .
b) Prove that for each $a \in \mathbf{N}$ the equation $\displaystyle \psi(x) = ax$ has a solution.
c) Find all $a \in \mathbf{N}$ such that the equation $\displaystyle \psi(x) = ax$ has a unique solution.

This was also

Solution

Let $d$ be a divisor of $n$ . We note that for $k \leq n/d$ , $(dk,n) = d$ if and only if $k$ is relatively prime to $n/d$ . It follows that each divisor $d$ of $n$ is found in the sum $\sum_{i=1}^{n}(k,n)$ exactly $\phi(n/d )$ times, where $\phi(m)$ is defined as the number of natural numbers less than or equal to $m$ and relatively prime to $m$ (the Euler Totient Function). It follows that

$\psi (n) = \sum_{k=1}^{n}(k,n) = \sum_{d \mid n} d \phi(n/d)$ .

In other words, $\psi$ is the convolution of the identity function $f: n \mapsto n$ and the $\phi$ function. Since these are both multiplicative functions, $\psi$ is also multiplicative, which is part (a) of the problem. For the next parts, we note that the equation $\psi(x) = ax$ is equivalent to the equation $\frac{\psi(x)}{x} = a$ .

We now note that for a prime $p$ and a non-negative integer $e$ ,

$\psi(p^k) = \sum_{i=0}^{e}p^i \cdot \phi(p^{e-i}) = p^e + \sum_{i=0}^{e-1}p^i(p^{e-i} - p^{e-i-1}) = p^e + e(p^e - p^{e-1})$ .

Since $\psi$ is multiplicative, if $\prod_{i=1}^k p_i^{e_i}$ is the prime factorization of $x$ , then

$\psi(x) = \prod_{i=1}^k [(e_i+1)p_i^{e_i} - e_i\cdot p_i^{e_i}]$ ,

and

$\frac{\psi(x)}{x} = \frac{\prod [(e_i+1)p_i^{e_i} - e_i \cdot p_i^{e_i}]}{\prod p_i^{e_i}} = \prod \left(e_i \frac{p_i-1}{p_i} + 1 \right)$ .

From this we can see that $x = 2^{2(a-1)}$ is always a solution to the equation $\frac{\psi(x)}{x} = a$ , which solves part (b). Let this solution to the equation be the canonical solution. However, we also note that if $2r +1$ is an odd postive integer, then $x = 3^{3r}$ is another solution to the equation. In particular, if $a$ has an odd prime factor $2r+1 > 1$ , then $x = 2^{2[a/(2r+1) -1]} \cdot 3^{3r}$ is a solution distinct from the canonical solution. Thus if the only solution to the equation $\frac{\psi(x)}{x} = a$ is canonical, then $a$ cannot have any odd divisors greater than 1, i.e., $a$ must be a power of 2.

We now claim that for $a = 2^k$ , the equation has no non-canonical solutions.

Lemma. Let $p_1, \ldots, p_k$ be odd primes, $e_1, \ldots, e_k$ be positive integers. If

$\prod_{i=1}^{k}\left(e_i \frac{p-1}{p} +1\right) = \frac{p}{q}$

and $p, q$ are relatively prime positive integers, then $p$ is divisible by an odd prime.

Proof. We first note that $e_i \frac{p_i-1}{p_i} + 1 \ge \frac{p_i-1}{p_i} + 1 > 1$ , so $\frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} +1 \right) > 1$ , or $p>q\ge 1$ . Thus $p$ must be divisible by some prime. But since $\frac{p}{q} = \prod \left( e_i \frac{p_i-1}{p_i} + 1 \right) = \frac{ \prod [e_i(p_i-1) + p_i] }{\prod p_i}$ , $p$ divides a product of odd numbers, so it cannot be divisible by 2. Hence $p$ is divisible by an odd prime. ∎

Now, suppose that for $a = 2^k$ there exists some non-canonical solution $x_1$ to the equation. Since $\psi(2^j) = \frac{j}{2} + 1$ , the only value of $x$ which is a power of 2 and is a solution is the canonical solution. Thus $x_1 = 2^c \cdot n$ , for some nonnegative integer $c$ and some odd integer $n>1$ . But by our lemma, $\frac{\psi(2^c\cdot n)}{2^c\cdot n} = \left(\frac{c+2}{2} \right) \cdot \frac{p}{q}$ , for some relatively prime $p$ and $q$ such that $p$ is odd. But since $\frac{\psi(x_1)}{x_1}$ is an integer and there are no factors in the denominator common to the odd prime which divides $p$ , $\frac{\psi(x_1)}{x_1} = 2^k$ must be divisible by an odd prime, a contradiction. Thus the canonical solution to the equation $\psi(x) = ax$ is unique if and only if $a$ is a power of 2. Q.E.D.