
3. Denote by $\mathbb{N}$ 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}$,

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

Find the least possible value of $f(2007)$.


Solution. Let $f$ be any function with the given property. We claim first of all that $f$ is injective. Indeed, if $f\left(y_{1}\right)=f\left(y_{2}\right)$, then for all natural $x$

$$
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 as $f(x)$ is a natural number it follows that $y_{1}=y_{2}$.

Taking $x=1$ in the given equation we get in particular $f(f(y))=y f(1)$, which for $y=1$ becomes $f(f(1))=f(1)$. As $f$ is injective, this means that

$$
f(1)=1 \text {, }
$$

so that for all natural $y$

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

The last relation implies, in particular, that the range of the function $f$ is the entire set $\mathbb{N}$. For any natural $z$ we can thus find $y$ such that $y=f(z)$ and at the same time $f(y)=z$; using again the given equation, we therefore get

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

An easy induction argument then implies that

$$
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)
$$

for any natural numbers $n$ and $x_{1}, x_{2}, \ldots, x_{n}$.

Next, we show that the image $f(p)$ of an arbitrary prime $p$ is also a prime. Assume that $f(p)=a b$, where $a$ and $b$ are natural numbers different from 1. By (2) a (3), then

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

Since $f$ is injective and $f(1)=1$, we must have $f(a)>1, f(b)>1$, contradicting the hypothesis that $p$ is a prime.

Since the decomposition of the number 2007 into prime factors is $2007=3^{2} \cdot 223$, we thus get by (3)

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

where both $f(3)$ and $f(223)$ are primes. If $f(3)=2$, then $f(2)=3$ by (2) so the least possible value for $f(223)$ is 5 , whence $f(2007) \geqslant 20$. If $f(3)=3$, then the least possible value of $f(223)$ is 2 and $f(2007) \geqslant 18$. It is easy to see that for any other choice of the values $f(3)$ a $f(223)$ we get $f(2007) \geqslant 18$.

We now show that there exists a function satisfying the conditions of the problem and such that $f(2007)=18$. Define $f$ in the following manner: For any natural number $x$, which we write as $x=2^{k} 223^{m} q$, where $k$ and $m$ are nonnegative integers and $q$ is a natural number coprime with 2 and 223 , set

$$
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 check that this function $f$ indeed 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 arbitrary 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 at the same time

$$
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 least possible value of $f(2007)$ is thus 18 .
