Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a function such that $f(mn) = f(m) + f(n)$ whenever $m$ and $n$ are relatively prime.

Question

This question is from a Brazilian math competition: "Olimpíada Cearense de Matemática (OCM)".

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a function such that $f(mn) = f(m) + f(n)$ whenever $m$ and $n$ are relatively prime. A natural number $m$ is called a bottleneck of $f$ if $n<m \implies f(n) < f(m)$ and $n>m \implies f(n) > f(m)$. If $f$ has infinity bottlenecks, shows that it is a strictly increasing function.

Answer 1

A strictly increasing function with the given properties cannot exist. Choose $f(2)$, then choose $p$ such that $p$ is an odd number and $p>f(2).$ Now we have $f(2p)=f(2)+f(p).$ If $f$ was strictly increasing, then $f(p), f(p+1), f(p+2),\ldots,f(2p)$ would be $p+1$ different natural numbers, hence $f(2p)-f(p)\geq p.$ On the other hand, $f(2p)-f(p)=f(2)<p.$ We have a contradiction.

Answer 2

As pointed out in the comments, since $(1,1)=1$, one has $$f(1)=f(1\cdot 1)=f(1)+f(1) \implies f(1)=0.$$ Hence $f$ can’t be strictly increasing because $$0<1 \implies f(0)<f(1) \implies f(0)<0,$$ and therefore $f(0) \notin \mathbb{N}$. A contradiction.