IMO 1998 SL 13

Origin: BUL

Problem

Determine the least possible value of f(1998), where f is a function from the set N of positive integers into itself such that for all m, n \inN, f(n2f(m)) = m[f(n)]2.

Solution

Denote by F the set of functions considered. Let f \inF, and let f(1) = a. Putting n = 1 and m = 1 we obtain f(f(z)) = a2z and f(az2) = f(z)2 for all z \inN. These equations, together with the original one, imply f(x)2f(y)2 = f(x)2f(ay2) = f(x2f(f(ay2))) = f(x2a3y2) = f(a(axy)2) = f(axy)2, or f(axy) = f(x)f(y) for all x, y \inN. Thus f(ax) = af(x), and we conclude that af(xy) = f(x)f(y) for all x, y \inN. (1) We now prove that f(x) is divisible by a for each x \inN. In fact, we inductively get that f(x)k = ak−1f(xk) is divisible by ak−1 for every k. If p\alpha and p\beta are the exact powers of a prime p that divide f(x) and a respectively, we deduce that k\alpha \geq(k −1)\beta for all k, so we must have \alpha \geq\beta for any p. Therefore a | f(x). Now we consider the function on natural numbers g(x) = f(x)/a. The above relations imply g(1) = 1, g(xy) = g(x)g(y), g(g(x)) = x for all x, y \inN. (2) Since g \inF and g(x) \leqf(x) for all x, we may restrict attention to the functions g only. Clearly g is bijective. We observe that g maps a prime to a prime. Assume to the contrary that g(p) = uv, u, v > 1. Then g(uv) = p, so either g(u) = 1 and g(v) = 1. Thus either g(1) = u or g(1) = v, which is impossible. We return to the problem of determining the least possible value of g(1998). Since g(1998) = g(2 \cdot 33 \cdot 37) = g(2) \cdot g(3)3 \cdot g(37), and g(2), g(3), g(37) are distinct primes, g(1998) is not smaller than 23 \cdot 3 \cdot 5 = 120. On the other hand, the value of 120 is attained for any function g satis- fying (2) and g(2) = 3, g(3) = 2, g(5) = 37, g(37) = 5. Hence the answer is 120.