The problem is as in title... I understand that, according to for example answers to this question, trivial solution is $f(x)=x$. However, I don't see is weakening condition $f(x\cdot y)=f(x)\cdot f(y)$ to not have to hold for all $x,y\in \mathbb{N}$, but only when $\gcd(x,y)=1$, making it possible to find any alternative solution?


  • $\begingroup$ There are lots of solutions. $f(2n)=2$ and $f(2n-1)=1$ for $n\ge1$ would be just one example. $\endgroup$ – Professor Vector Oct 5 '17 at 9:21
  • $\begingroup$ I'm very sorry, forgot to mention an additional requirement and that is that the function has to be strictly increasing: $x>y\implies f(x)>f(y)$. I've edited the title accordingly now. Any suggestions for this case? $\endgroup$ – Crni Oct 5 '17 at 13:29
  • $\begingroup$ With that correction, I feel there will be only the "trivial" solution $f(n)=n$, but showing that will be very far from trivial. $\endgroup$ – Professor Vector Oct 5 '17 at 14:05

You can define $f(n)$ as the greatest power of $2$ that divides $n$.

  • 1
    $\begingroup$ $1=f(2\cdot3)\neq f(2)\cdot f(3)=2\cdot 1$ $\endgroup$ – Professor Vector Oct 5 '17 at 9:25
  • $\begingroup$ @ProfessorVector Thanks. I have corrected my answer. $\endgroup$ – José Carlos Santos Oct 5 '17 at 9:31
  • $\begingroup$ Forgot to mention that function $f(x)$ has to be increasing, sorry. $\endgroup$ – Crni Oct 5 '17 at 14:06
  • $\begingroup$ That's not a minor detail! $\endgroup$ – José Carlos Santos Oct 5 '17 at 14:30
  • $\begingroup$ I know, I'm very sorry for this omission. $\endgroup$ – Crni Oct 5 '17 at 14:56

You can define $f(x)$ to be whatever you like in all prime powers except 2 (where it is already defined), and that would still be OK. Then use multiplicity to reconstruct $f$ in all other integer points.

  • Trivial solution: $f(p^n)=p^n$.
  • Solution of Professor Vector: $\begin{cases}f(2^n)=2,\\f(p^n)=1, p\ne2\end{cases}$
  • Solution of José Carlos Santos: $\begin{cases}f(2^n)=2^n,\\f(p^n)=1, p\ne2\end{cases}$

There are plenty of other possibilities. How about letting $f(p^n)=n+1$ (which is consistent with $f(2)=2$)? That would be the divisor function $\sigma_0$.

  • $\begingroup$ Forgot to mention that function $f(x)$ has to be increasing, sorry. $\endgroup$ – Crni Oct 5 '17 at 14:06

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.