Function Recursion Solution
Let $ f $ be a function taking the positive integers to the positive integers, such that
\[f(mf(n)) = nf(m)\]for all positive integers $ m $ and $ n $. Find the smallest possible value of $ f(2007) $.
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
Setting $ m = n, $ we get
\[f(nf(n)) = nf(n).\]Thus, $ nf(n) $ is a fixed point for all positive integers $ n $. (In other words, $ x = nf(n) $ satisfies $ f(x) = x $.)
Setting $ m = 1, $ we get
\[f(f(n)) = nf(1).\]If $ n $ is a fixed point (which we know exists), then $ n = nf(1), $ so $ f(1) = 1 $. Hence,
\[f(f(n)) = n\]for all positive integer $ n $. This equation tells us that the function $ f $ is surjective.
Furthermore, if $ f(a) = f(b), $ then
\[f(f(a)) = f(f(b)),\]so $ a = b $. Therefore, $ f $ is injecitve, which means that $ f $ is bijective.
Replacing $ n $ with $ f(n) $ in the given functional equation yields
\[f(m f(f(n))) = f(n) f(m).\]Since $ f(f(n)) = n, $
\[f(mn) = f(n) f(m) \quad (*)\]for all positive integers $ m $ and $ n $.
Taking $ m = n = 1 $ in $ (*), $ we get
\[f(1) = f(1)^2,\]so $ f(1) = 1 $.
Recall that for a positive integer $ n, $ $ \tau(n) $ stands for the number of divisors of $ n $. Thus, given a positive integer $ n, $ there are $ \tau(n) $ ways to write it in the form
\[n = ab,\]where $ a $ and $ b $ are positive integers. Then
\[f(n) = f(ab) = f(a) f(b).\]Since$ f $ is a bijection, each way of writing $ n $ as the product of two positive integers gives us at least one way of writing $ f(n) $ as the product of two positive integers, so
\[\tau(f(n)) \ge \tau(n).\]Replacing $ n $ with $ f(n), $ we get
\[\tau(f(f(n)) \ge \tau(f(n)).\]But $ f(f(n)) = n, $ so
\[\tau(n) \ge \tau(f(n)).\]Therefore,
\[\tau(f(n)) = \tau(n)\]for all positive integers $ n $.
If $ n $ is a prime $ p, $ then
\[\tau(f(p)) = \tau(p) = 2.\]This means $ f(p) $ is also prime. Hence, if $ p $ is prime, then $ f(p) $ is also prime.
Now,
\[f(2007) = f(3^2 \cdot 223) = f(3)^2 f(223).\]We know that both $ f(3) $ and $ f(223) $ are prime.
If $ f(3) = 2, $ then $ f(2) = 3, $ so $ f(223) \ge 5, $ and
\[f(3)^2 f(223) \ge 2^2 \cdot 5 = 20.\]If $ f(3) = 3, $ then
\[f(3)^2 f(223) \ge 3^2 \cdot 2 = 18.\]If $ f(3) \ge 5, $ then
\[f(3)^2 f(223) \ge 5^2 \cdot 2 = 50.\]So $ f(2007) $ must be at least 18. To show that the 18 is the smallest possible value of $ f(2007), $ we must construct a function where $ f(2007) = 18 $. Given a positive integer $ n, $ take the prime factorization of $ n $ and replace every instance of 2 with 223, and vice-versa (and all other prime factors are left alone). For example,
\[f(2^7 \cdot 3^4 \cdot 223 \cdot 11^5) = 223^7 \cdot 3^4 \cdot 2 \cdot 11^5.\]It can be shown that this function works. Thus, the smallest possible value of $ f(2007) $ is $ \boxed{18} $.