Consider all functions f from the set of all positive integers into itself satisfying f(t2f(s)) = s f(t)2 for all s and t. Determine the least possible value of f(1998).
Answer
120
Solution
Let f(1) = k. Then f(kt2) = f(t)2 and f(f(t)) = k2t. Also f(kt)2 = 1·f(kt)2 = f(k3t2) = f(12f(f(kt2))) = k2f(kt2) = k2f(t)2. Hence f(kt) = k f(t).
By an easy induction knf(tn+1) = f(t)n+1. But this implies that k divides f(t). For suppose the highest power of a prime p dividing k is a > b, the highest power of p dividing f(t). Then a > b(1 + 1/n) for some integer n. But then na > (n + 1)b, so kn does not divide f(t)n+1. Contradiction.
Let g(t) = f(t)/k. Then f(t2f(s)) = f(t2kg(s)) = k f(t2g(s) = k2g(t2g(s)), whilst s f(t)2 = k2s f(t)2. So g(t2g(s)) = s g(t)2. Hence g is also a function satisfying the conditions which evidently has smaller values than f (for k > 1). It also satisfies g(1) = 1. Since we want the smallest possible value of f(1998) we may restrict attention to functions f satisfying f(1) = 1.
Thus we have f(f(t) = t and f(t2) = f(t)2. Hence f(st)2 = f(s2t2) = f(s2f(f(t2))) = f(s)2f(t2) = f(s)2f(t)2. So f(st) = f(s) f(t).
Suppose p is a prime and f(p) = m·n. Then f(m)f(n) = f(mn) = f(f(p)) = p, so one of f(m), f(n) = 1. But if f(m) = 1, then m = f(f(m)) = f(1) = 1. So f(p) is prime. If f(p) = q, then f(q) = p.
Now we may define f arbitarily on the primes subject only to the conditions that each f(prime) is prime and that if f(p) = q, then f(q) = p. For suppose that s = p1a1...prar and that f(pi) = qi. If t has any additional prime factors not included in the qi, then we may add additional p's to the expression for s so that they are included (taking the additional a's to be zero). So suppose t = q1b1...qrbr.Then t2f(s) = q12b1+a1 ...qr2br+ar and hence f(t2f(s) = p12b1+a1 ...pr2br+ar = s f(t)2.
We want the minimum possible value of f(1998). Now 1998 = 2.33.37, so we achieve the minimum value by taking f(2) = 3, f(3) = 2, f(37) = 5 (and f(37) = 5). This gives f(1998) = 3·235 = 120.
© John Scholes
jscholes@kalva.demon.co.uk
26 Oct 1998
Last corrected/updated 20 Aug 03