IMO 2004 SL N2

Origin: RUS | Category: Number Theory

Problem

The function \psi from the set N of positive integers into itself is defined by the equality \psi(n) = n  k=1 (k, n), n \inN, where (k, n) denotes the greatest common divisor of k and n. (a) Prove that \psi(mn) = \psi(m)\psi(n) for every two relatively prime m, n \in N. (b) Prove that for each a \inN the equation \psi(x) = ax has a solution. (c) Find all a \inN such that the equation \psi(x) = ax has a unique solution.

Solution

Let n be a natural number. For each k = 1, 2, . . ., n, the number (k, n) is a divisor of n. Consider any divisor d of n. If (k, n) = n/d, then k = nl/d for some l \inN, and (k, n) = (l, d)n/d, which implies that l is coprime to d and l \leqd. It follows that (k, n) is equal to n/d for exactly ϕ(d) natural numbers k \leqn. Therefore \psi(n) = n  k=1 (k, n) =  d|n ϕ(d)n d = n  d|n ϕ(d) d . (1) (a) Let n, m be coprime. Then each divisor f of mn can be uniquely expressed as f = de, where d | n and e | m. We now have by (1) \psi(mn) = mn  f|mn ϕ(f) f = mn  d|n, e|m ϕ(de) de = mn  d|n, e|m ϕ(d) d ϕ(e) e

⎛ ⎝n  d|n ϕ(d) d ⎞ ⎠ ⎛ ⎝m  e|m ϕ(e) e ⎞ ⎠ = \psi(m)\psi(n).

(b) Let n = pk, where p is a prime and k a positive integer. According to (1), \psi(n) n

k  i=0 ϕ(pi) pi = 1 + k(p −1) p . Setting p = 2 and k = 2(a −1) we obtain \psi(n) = an for n = 22(a−1). (c) We note that \psi(pp) = pp+1 if p is a prime. Hence, if a has an odd prime factor p and a1 = a/p, then x = pp22a1−2 is a solution of \psi(x) = ax different from x = 22a−2. Now assume that a = 2k for some k \inN. Suppose x = 2\alphay is a positive integer such that \psi(x) = 2kx. Then 2\alpha+ky = \psi(x) = \psi(2\alpha)\psi(y) = (\alpha+2)2\alpha−1\psi(y), i.e., 2k+1y = (\alpha+2)\psi(y). We notice that for each odd y, \psi(y) is (by definition) the sum of an odd number of odd summands and therefore odd. It follows that \psi(y) | y. On the other hand, \psi(y) > y for y > 1, so we must have y = 1. Consequently \alpha = 2k+1−2 = 2a−2, giving us the unique solution x = 22a−2. Thus \psi(x) = ax has a unique solution if and only if a is a power of 2.