Canadian Mathematical Olympiad

Solution:
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 the 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(2x)) = \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(f(x)) = x$ 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.