2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I am new to Stack Exchange, so I apologize for the incomplete title of the question. $\endgroup$ – himanshu mallick Jul 10 '18 at 18:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But $f(n)=2^k\quad k\in\mathbb{N}$ works. Why does your argument fail for this case? $\endgroup$ – himanshu mallick Jul 12 '18 at 8:41
  • $\begingroup$ How does it work? $2^{k-1}\neq 2^{k-1}+2^{k-1}$. $\endgroup$ – Batominovski Jul 12 '18 at 9:55
  • $\begingroup$ Oh, I am so sorry, I stupidly overlooked the LHS. $\endgroup$ – himanshu mallick Jul 12 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.