Find all functions $f: \mathbb{N}\to\mathbb{N}$ such that $f(x)=f(x^y)$

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

$$f(x)=f(x^y)$$

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

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

• $f$ could give the prime decomposition of a number. – amcalde Mar 16 '16 at 12:09
• 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 – vrugtehagel Mar 16 '16 at 12:10

1 Answer

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$).