# Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $\varphi(f(x+y))=\varphi(f(x))+\varphi(f(y))\quad\forall x,y\in\mathbb{N}$

I was studying about Cauchy's Functional Equation, and suddenly I had the following question in my mind: Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $$\varphi(f(x+y))=\varphi(f(x))+\varphi(f(y))\quad\forall x,y\in\mathbb{N}$$ Here, $\varphi(n)$ is Euler's Totient Function.

I first tried to find some trivial cases, and intuitively I felt that if $f(x)=c$, where $c$ is a constant, then $c$ must be a perfect power of a prime. And, in this case, the only trivial solution I found was $f(x)=2^k$ where $k$ is a positive integer. I really have no idea whether other solutions do exist or not.

If $0$ is in $\mathbb{N}$ with the convention $\varphi(0)=0$, then there is a unique solution $f(n)=0$ for every $n\in\mathbb{N}$. From now on, I assume that $\mathbb{N}$ is defined to be $\{1,2,3,\ldots\}$. I claim that there does not exist such a function $f$.
Suppose on the contrary that $f$ exists. Let $g:=\varphi\circ f$. Then, $g$ satisfies Cauchy's functional equation. That is, there exists $c\in\mathbb{N}$ such that $g(n)=cn$ for all $n\in\mathbb{N}$.
Let $d_1,d_2,\ldots,d_k$ be all natural numbers that divide $c$. Pick pairwise distinct primes $p_1,p_2,\ldots,p_{2k}$ that do not divide $c$. Consider the system of congruences $$d_ix\equiv-1\pmod{p_{2i-1}p_{2i}}$$ for $i=1,2,\ldots,k$. This congruence has a unique solution $$x\equiv x_0\pmod{P}\,,$$ where $P:=p_1p_2\cdots p_{2k}$ and $x_0\in\mathbb{Z}_{>0}$. By Dirichtlet's Theorem, there exists a prime natural number $p>c$ such that $p\equiv x_0\pmod{P}$, noting that $\gcd(x_0,P)=1$. It follows that the equation $$\varphi(N)=cp$$ has no solution $N\in\mathbb{N}$. Thus, $\varphi\big(f(p)\big)=g(p)=cp$ is impossible.
• But $f(n)=2^k\quad k\in\mathbb{N}$ works. Why does your argument fail for this case? Jul 12 '18 at 8:41
• How does it work? $2^{k-1}\neq 2^{k-1}+2^{k-1}$. Jul 12 '18 at 9:55