6. let $P$ be the set of the first 2009 prime numbers and let $X$ be the set of all natural numbers which have only prime factors from $P$. Determine all natural numbers $k$ for which a function $f: X \rightarrow X$ exists which satisfies the following equation for all $m, n \in X$:

$$
f(m f(n))=f(m) n^{k}
$$

## Solution
Such a function exists if and only if $k$ is a square number.

If $k=l^{2}$ is first a square, then the function $f(n)=n^{l}$ has the desired property, because both sides of the equation are $m^{l} n^{k}$.

Conversely, let such an $f$ exist. Let $a=f(1) \in X$. Set $n=1$, then $f(a m)=f(m)$ follows for all $m \in X$. If you now replace $n$ with an in the original equation, then $f(m) n^{k}=f(m f(n))=f(m f(a n))=f(m)(a n)^{k}$, i.e. $a=f(1)=1$. With $m=1$ now follows

$$
f(f(n))=n^{k} \quad \text { for all } n \in X \text {. }
$$

If you replace $n$ with $f(n)$ here, then $f\left(n^{k}\right)=f(n)^{k}$ also follows for all $n$. If you replace $m$ with $f(m)$ in the original equation and apply $f$ to both sides, then the following applies with what has just been shown

$$
(f(m) f(n))^{k}=f(f(f(m) f(n)))=f\left((m n)^{k}\right)=f(m n)^{k}
$$

so

$$
f(m n)=f(m) f(n) \quad \text { for all } m, n \in X \text {. }
$$

The following conclusions can now be drawn from (2) and (3):

- If $n \neq 1$, then $f(n) \neq 1$. Otherwise $n^{k}=f(f(n))=f(1)=1$ would be a contradiction.
- If $m, n$ are divisors, then also $f(m)$ and $f(n)$. If $d>1$ were a common divisor of these two numbers, then it follows from (3) that $f(d)>1$ would be a common divisor of $f(f(a))=a^{k}$ and $f(f(b))=b^{k}$, contradiction.
- For every prime number $p \in P$, $f(p)$ is a power of a prime number $q \in P$. Otherwise $f(p)$ would be a product of two divisors $>1$ and therefore also $p^{k}=f(f(p))$.
- We can therefore define a function $g: P \rightarrow P$ as follows: For each prime number $p \in P$, let $g(p) \in P$ be the prime number of which $f(p)$ is a power. Because of (2), $g$ is now an involution, i.e. $g \circ g=i d_{P}$. Since $P$ has an odd number of elements, $g$ must have a fixed point $p$.
- Thus $f(p)=p^{l}$ with a natural number $l$ and with (3) therefore $p^{k}=f(f(p))=$ $f\left(p^{l}\right)=\left(p^{l}\right)^{l}=p^{l^{2}}$. Thus $k=l^{2}$ is a square number, as claimed.

Note: The same result applies if 2009 is replaced by any odd natural number $r$. For even $r$, however, such a function $f$ exists for every $k$. To construct it, partition $P$ into $r / 2$ disjoint pairs $\left(p_{i}, q_{i}\right)$ of prime numbers. The uniquely determined function $f: X \rightarrow X$ with

- $f(m n)=f(m) f(n)$ for all $m, n \in X$,
- $f\left(p_{i}\right)=q_{i}$ and $f\left(q_{i}\right)=p_{i}^{k}$

then satisfies the equation $f(m f(n))=f(m) n^{k}$ for all $m, n \in X$.