Problem 1613

Define an $m \in \mathbb{N}$ to be good if $f(m)=m$ for all such $f$. It will be shown that $m$ is good if and only if $m$ has two or more distinct prime divisors. Let $P(x, y)$ denote the assertion

$$\operatorname{gcd}(f(f(x)), f(x+y))=\operatorname{gcd}(x, y)$$

for a pair $x, y \in \mathbb{N}$. Let $x$ be a positive integer with two or more distinct prime divisors and let $p^{k}$ be largest power of one of these prime divisors such that $p^{k} \mid x$. If $x=p^{k} \cdot q$, then $p^{k}$ and $q$ are relatively prime and $x>p^{k}, q>1$. By $P(q, x-q)$,

$$\operatorname{gcd}(f(f(q)), f(x-q+q))=\operatorname{gcd}(f(f(q)), f(x))=\operatorname{gcd}(q, x-q)=q$$

which implies that $q \mid f(x)$. By $P\left(p^{k}, x-p^{k}\right)$,

$$\operatorname{gcd}\left(f\left(f\left(p^{k}\right)\right), f\left(x-p^{k}+p^{k}\right)\right)=\operatorname{gcd}\left(f\left(f\left(p^{k}\right)\right), f(x)\right)=\operatorname{gcd}\left(p^{k}, x-p^{k}\right)=p^{k}$$

which implies that $p^{k} \mid f(x)$. Since $p^{k}$ and $q$ are relatively prime, $x=p^{k} \cdot q$ divides $f(x)$, which implies that $f(x) \geq x$. Now assume for contradiction that $f(x)>x$. Let $y=f(x)-x>0$ and note that, by $P(x, y)$, it follows that

$$f(f(x))=\operatorname{gcd}(f(f(x)), f(x+f(x)-x))=\operatorname{gcd}(x, f(x)-x)=\operatorname{gcd}(x, f(x)) .$$

Therefore $f(f(x)) \mid x$ and $f(f(x)) \mid f(x)$. By $P(x, x)$, it follows that

$$\operatorname{gcd}(f(f(x)), f(2 x))=\operatorname{gcd}(x, x)=x$$

This implies that $x \mid f(f(x))$, which when combined with the above result, yields that $f(f(x))=x$. Since $x \mid f(x)$ and $x$ is divisible by at least two distinct prime numbers, $f(x)$ is also divisible by at least two distinct prime numbers. As shown previously, this implies that $f(x) \mid f(f(x))=x$, which is a contradiction since $f(x)>x$. Therefore $f(x)=x$ for all positive integers $x$ with two or more distinct prime divisors.

Now it will be shown that all $m \in \mathbb{N}$ such that either $m$ has one prime divisor or $m=1$ are not good. In either case, let $m=p^{k}$ where $k \geq 0$ and $p$ is a prime number and consider the function satisfying that $f\left(p^{k}\right)=p^{k+1}, f\left(p^{k+1}\right)=p^{k}$ and $f(x)=x$ for all $x \neq p^{k}, p^{k+1}$. Note that this function also satisfies that $f(f(x))=x$ for all positive integers $x$. If $x+y \neq p^{k}, p^{k+1}$, then $P(x, y)$ holds by the Euclidean

algorithm since $f\left(f((x))=x\right.$ and $f(x+y)=x+y$. If $x+y=p^{k+1}$, then $P(x, y)$ is equivalent to $\operatorname{gcd}\left(x, p^{k}\right)=\operatorname{gcd}\left(x, p^{k+1}-x\right)=\operatorname{gcd}\left(x, p^{k+1}\right)$ for all $x<p^{k+1}$ which holds since the greatest power of $p$ that can divide $x$ is $p^{k}$. If $x+y=p^{k}$, then $P(x, y)$ is equivalent to $\operatorname{gcd}\left(x, p^{k+1}\right)=\operatorname{gcd}\left(x, p^{k}-x\right)=\operatorname{gcd}\left(x, p^{k}\right)$ for all $x<p^{k}$ which holds as shown above. Note that if $m=1$ then this case cannot occur. Since this function satisfies $P(x, y), m$ is good if and only if $m$ has two or more distinct prime divisors.