Find all functions $f:\mathbb{N}\to\mathbb{N}$ such that


for all $x,y\in\mathbb{N}$.

I'm not intrested in the trivial solution $f(x)=k$, where $k\in\mathbb{N}$.

  • $\begingroup$ $f$ could give the prime decomposition of a number. $\endgroup$ – amcalde Mar 16 '16 at 12:09
  • 4
    $\begingroup$ Can't you just assign any value to $f(k)$ if $k$ is not a perfect power, and if $x=k^n$ is a perfect power then $f(x)=f(k^n)=f(k)$? I think I don't fully understand the problem here $\endgroup$ – vrugtehagel Mar 16 '16 at 12:10

As vrugtehagel said, you can assign an arbitrary value to $f(x)$ if $x$ is not a perfect power and then define $f(x^y)=f(x)$ for all the powers of $x$, or more precisely, for every $x>1$, you can write the prime factorization of $x$ $$ x = p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k} $$ then compute $$e = GCD(e_1,e_2,\dots,e_k)$$

$e$ is the largest possible exponent when $x$ is expressed as a perfect power.

If $e=1$, then $x$ is not a perfect power, and you can assign to $f(x)$ whatever value you like, say a function of $x$ or an arbitrary value.

If $e>1$, then you define $f(x)=f(x^{1/e})$.

The only check we must perform is the following. If a value $z$ can be expressed in two ways, say as $n^m$ and $s^t$, we must be sure that $f(z)=f(n^m)=f(n)$ and $f(z)=f(s^t)=f(s)$ coincide.

But this is not a problem, because if a number $z$ can be expressed in that way, then $n$ and $s$ must be both powers of a number $w$ (that may coincide with $n$ or $s$).

| cite | improve this answer | |

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.