3. Let $\mathbb{N}$ denote the set of all natural numbers, and consider all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that for any $x, y \in \mathbb{N}$, the following holds:

$$
f(x f(y))=y f(x) .
$$

Determine the smallest possible value of $f(2007)$.

(P. Calábek)
Solution. Consider any function $f$ with the required properties. First, we will show that it is injective. If $f\left(y_{1}\right)=f\left(y_{2}\right)$, then for all natural numbers $x$ we have

$$
y_{1} f(x)=f\left(x f\left(y_{1}\right)\right)=f\left(x f\left(y_{2}\right)\right)=y_{2} f(x) \text {, }
$$

and since $f(x)$ is a natural number, it follows that $y_{1}=y_{2}$, which means that the function $f$ is injective.

By choosing $x=1$ in the given equation, we get $f(f(y))=y f(1)$, which for $y=1$ gives $f(f(1))=f(1)$. Since $f$ is injective, it follows that

$$
f(1)=1
$$

and thus for all natural numbers $y$ we also have

$$
f(f(y))=y
$$

From the above relation, it follows that the range of the function $f$ is the entire set $\mathbb{N}$. Therefore, for any natural number $z$, we can find $y$ such that $y=f(z)$ and simultaneously $f(y)=z$, so according to the relation from the problem, we have

$$
f(x z)=f(x(f(y))=y f(x)=f(z) f(x) .
$$

From this, it is easy to deduce by mathematical induction that for all natural numbers $n$, $x_{1}, x_{2}, \ldots, x_{n}$ we have

$$
f\left(x_{1} x_{2} \ldots x_{n}\right)=f\left(x_{1}\right) f\left(x_{2}\right) \ldots f\left(x_{n}\right) .
$$

We will show that the image $f(p)$ of any prime number $p$ is also a prime number. Suppose that $f(p)=a b$, where $a, b$ are natural numbers different from one. According to (2) and (3), we have

$$
p=f(f(p))=f(a b)=f(a) f(b) .
$$

Since the function $f$ is injective and $f(1)=1$, it follows that $f(a)>1, f(b)>1$, which contradicts the assumption that $p$ is a prime number.

Since $2007=3^{2} \cdot 223$ is the prime factorization of 2007, we get from (3)

$$
f(2007)=f^{2}(3) f(223),
$$

where both numbers $f(3)$ and $f(223)$ are prime numbers. If $f(3)=2$, then according to (2) we have $f(2)=3$ and the smallest possible value of $f(223)$ is 5, so $f(2007) \geqq 20$. If $f(3)=3$, the smallest possible value of $f(223)$ is 2 and we have $f(2007) \geqq 18$. It is easy to see that for any other choice of values of $f(3)$ and $f(223)$, we have $f(2007) \geqq 18$.

We will show that there exists a function satisfying the problem, for which $f(2007)=18$. Define the function $f$ as follows: For any natural number $x$, which we write as $x=2^{k} 223^{m} q$, where $k$ and $m$ are non-negative integers and $q$ is a natural number coprime with 2 and 223, we define the value of $f(x)$ by the relation

$$
f\left(2^{k} 223^{m} q\right)=2^{m} 223^{k} q .
$$

Then $f(2007)=f\left(223 \cdot 3^{2}\right)=2 \cdot 3^{2}=18$. We will verify that this function $f$ has the required property. Let $x=2^{k_{1}} 223^{m_{1}} q_{1}$ and $y=2^{k_{2}} 223^{m_{2}} q_{2}$ be any natural numbers written in the above form. Then

$$
\begin{aligned}
f(x f(y)) & =f\left(2^{k_{1}} 223^{m_{1}} q_{1} f\left(2^{k_{2}} 223^{m_{2}} q_{2}\right)\right)=f\left(2^{k_{1}+m_{2}} 223^{m_{1}+k_{2}} q_{1} q_{2}\right)= \\
& =2^{k_{2}+m_{1}} 223^{m_{2}+k_{1}} q_{1} q_{2}
\end{aligned}
$$

and simultaneously

$$
y f(x)=2^{k_{2}} 223^{m_{2}} q_{2} f\left(2^{k_{1}} 223^{m_{1}} q_{1}\right)=2^{k_{2}+m_{1}} 223^{m_{2}+k_{1}} q_{1} q_{2} .
$$

The smallest possible value of the number $f(2007)$ is 18.

Note. From the above solution, it follows that any function $f$ that satisfies the given functional equation is determined by some bijection $\varphi$ of the set of prime numbers onto itself, which for each prime number $p$ satisfies the equality $\varphi(\varphi(p))=p$, and is defined by the formula

$$
\begin{aligned}
f(1) & =1 \\
f\left(p_{1}^{k_{1}} p_{2}^{k_{2}} \ldots p_{m}^{k_{m}}\right) & =\varphi\left(p_{1}\right)^{k_{1}} \varphi\left(p_{2}\right)^{k_{2}} \ldots \varphi\left(p_{m}\right)^{k_{m}}
\end{aligned}
$$

where $p_{i}$ are distinct prime numbers and $k_{i}$ are non-negative integers. Each bijection $\varphi$ with the above property partitions the set of prime numbers into a union of disjoint one-element and two-element sets such that for each of them of the form $\{p\}$ we have $\varphi(p)=p$ and for each of them of the form $\left\{p_{1}, p_{2}\right\}$ we have $\varphi\left(p_{1}\right)=p_{2}, \varphi\left(p_{2}\right)=p_{1}$. Conversely, any such partition determines a suitable bijection $\varphi$.