may some brave soul write this up

@above I gotchu

Nice problem . The answers are $\boxed{\text{any non prime power positive integers } n.}$ Let $P(x,y)$ be the assertion of $x$ and $y$ to the given functional equation. Claim 01. $f(f(x)) = x$ for all $x \in \mathbb{N}$. Proof. $P(x,x)$ gives us $x = \gcd(f(f(x)), f(2x))$. Thus, $x \mid f(f(x))$ and $x \mid f(2x)$. Now, $P(x, \textcolor{red}{2f(f(x)) - x})$ which is allowed since both plugs are positive since $f(f(x)) \ge x$ from the first claim, and we get \[ f(f(x)) = \gcd(\textcolor{blue}{f(f(x))}, f(\textcolor{blue}{2f(f(x))}) = \gcd(x,2f(f(x))) \]Thus, $f(f(x)) \mid x$. Therefore, we have $f(f(x)) = x$ for all $x \in \mathbb{N}$. Thus, we have deduced that if $f$ is Canadian, then $f$ is an involutive function $f: \mathbb{N} \to \mathbb{N}$ and \[ \gcd(x,f(y)) = \gcd(x,y) \]for any $x < y$ in natural numbers. Let $Q(x,y)$ be the assertion of $x$ and $y$ to the functional equation above. We call an integer $m$ to be fun if for any Canadian function $f$, we have $f(m) = m$, and not fun otherwise. Claim 02. Any prime powers is not fun. Proof. Consider the following function to show that both $p^{k - 1}, p^k$ are not fun. \begin{align*} f(n) = \begin{cases} p^k \ \text{if } n = p^{k - 1} \\ p^{k - 1} \ \text{if } n = p^k \\ n \ \text{otherwise.} \end{cases} \end{align*}for any prime number $p$. We claim that this is a Canadian function. For any $Q(x,y)$ such that $x,y \in \mathbb{N}_{\not= p^k, p^{k - 1}}$, then indeed we have \[ \gcd(x,f(y)) = \gcd(x,y) \]Now, just notice that for any integer $x < p^k$ and $y \in \{ p^{k - 1}, p^k \}$, then we have \[ \gcd(x,p^{k - 1}) = \gcd(x,p^k) \]since $\nu_p(x) \le k - 1$ for any such integer, and therefore we are done since \[ \text{min}(\nu_p(x), k - 1) = \nu_p(x) = \text{min}(\nu_p(x), k). \] Claim 03. For any non prime powers $\ell$, then $\ell \mid f(\ell)$. Proof. First of all, we prove that $x \mid f(xy)$ for any $x,y \in \mathbb{N}_{\ge 2}$. Notice that $Q(x,kx)$ where $k \ge 2$ gives us \[ \gcd(x,f(kx)) =\gcd(x,kx) = x \]Therefore, $x \mid f(kx)$ for all $k \ge 2$. Now, if $\ell$ is a composite number, then we could let $\ell = a \cdot b$ where $a,b > 1$ and $\gcd(a,b) = 1$, therefore from our lemma, we have $a \mid f(\ell)$ and $b \mid f(\ell)$. Since $\gcd(a,b) = 1$, then we conclude that $\ell \mid f(\ell)$ for any non prime powers $\ell$. Claim 04. Any composite number that is not a prime power is cute. Proof. First of all, notice that if $a$ is not a prime power, then $f(a)$ is not a prime power as well, since $a \mid f(a)$. Therefore, we conclude that $f(a) \mid f(f(a)) = a$. However, we know that $a \mid f(a)$. Therefore, we have $f(a) = a$ for any non prime powers $a$, proving that $a$ is cute for any non prime powers $a$.

Canadian MO 2021 P4 wrote: A function $f$ from the positive integers to the positive integers is called Canadian if it satisfies $$\gcd\left(f(f(x)), f(x+y)\right)=\gcd(x, y)$$for all pairs of positive integers $x$ and $y$. Find all positive integers $m$ such that $f(m)=m$ for all Canadian functions $f$. Interesting. Take $y \rightarrow y-x$ to transform the given equation to $\gcd (f(f(x)),f(y))=(x,y)$, with $y>x$. Let this equation be $P(x,y)$. Call each number $m$ satisfying $f(m)=m$ for all Canadian functions $f$ magical. We start off with a Claim: Claim 1: $f(f(x))=x$. Proof: $P(x,2x)$ implies that $x \mid f(f(x))$ and $x \mid f(2x)$ for all $x$ . Suppose that $p$ is a prime and $v_p(x)=k$. Suppose that $v_p(f(f(x))) >k$ for some $x$. Take a positive integer $s$ such that $sp^{k+1}>x$ and note that $f(2sp^{k+1}) \geq sp^{k+1}>x$, since $x \mid f(2x)$, therefore $P(x,f(2sp^{k+1}))$ implies $$\gcd(f(f(x)),f(f(2sp^{k+1})))=(x,f(2sp^{k+1}))$$ Now, note that $p^{k+1} \mid f(f(x))$ and $p^{k+1} \mid 2sp^{k+1} \mid f(f(2sp^{k+1}))$, therefore the LHS of the above is divisible by $p^{k+1}$, which implies that $p^{k+1} \mid (x,f(2sp^{k+1}))$, thus $p^{k+1} \mid x$, a contradiction. Therefore, $v_p(x)=v_p(f(f(x))$ for all primes $p$, therefore $f(f(x))=x$ for all $x$. $\blacksquare$ To the problem, $P(x,y)$ rewrites as $\gcd(x,f(y))=\gcd(x,y)$ for all $x<y$. Let this assertion be $Q(x,y)$. We make now two more Claims: Claim 2: $x \mid f(x)$ for all that are not prime powers. Proof: Let $r$ be a prime and $v_r(x)=\ell$. Then, if $x$ is not a prime power we may assume that $f(x) \neq r^\ell$, therefore $f(x)>r^\ell$. Then, $P(r^\ell,f(x))$ implies $$\gcd(r^\ell,f(f(x)))=\gcd(r^\ell,f(x)),$$and since $r^\ell \mid x \mid f(f(x))$, we infer $$r^\ell \mid \gcd(r^\ell,f(f(x)))=\gcd(r^\ell,f(x)) \Rightarrow r^\ell \mid f(x)$$ Therefore, $v_r(f(x)) \geq v_r(x)$ for all primes $r$, implying that $x \mid f(x)$ for all non-prime powers $x$. $\blacksquare$ Claim 3: All non-prime powers are magical. Proof: Indeed, take such a number $x$ and notice that, since $x \mid f(x)$ from Claim 2, we see that $f(x)$ cannot be a prime power, as otherwise $x$ would be, too. Therefore, $f(x) \mid f(f(x))$, resulting in $$x \mid f(x) \mid f(f(x))=x,$$therefore all non-prime powers are magical. $\blacksquare$ Now, in order to prove that prime powers are not magical, consider the following construction: \begin{align*} f(x) = \begin{cases} p^\ell \ \text{if} \, x = p^{k} \\ p^{k} \ \text{if } x = p^\ell \\ x \ \text{if} \, x \, \neq p^k \, \text{and} \, x \neq p^\ell, \end{cases} \end{align*}where $p$ is a prime and $k \neq \ell$. It is easy to check that this function is involutive and satisfies $Q(x,y)$, therefore we conclude that prime powers are not magical. Therefore, the answer is $\boxed{\text{all numbers that are not prime powers}}$ @below I am dumb. Whoops.

@above I think that generally 1 is a prime power as well since $1 = p^0$

Solution with p_square and Arwen713, first we show that any non prime power goes to itself. Let $n\ne p^\alpha\mid n$ then we let $n=p^{\alpha}k$. Now, let $x=p^{\alpha}$ and $y=p^{\alpha}(k-1)$. Thus, $p^{\alpha}\mid f(x+y)=f(n)$. Thus, doing this for all prime divisors of $n$, we get $n\mid f(n)$. Now, if $f(n)\ne n$, let $x=n$ and $y=f(n)-n$, now $f(f(n))=gcd(n,f(n)-n)=gcd(n,f(n))$ but we have $n\vert f(n)\vert f(f(n))\implies n=f(n)=f(f(n))$ and the claim follows. Now, if $n$ is a prime power. Let it be $p^{\alpha}$. We construct the following Canadian function. For all $n\ne p^{\alpha}, p^{\alpha+1}$ let $f(n)=n$ and for let $f(p^{\alpha})=p^{\alpha+1}$ and $f(p^{\alpha+1})=p^{\alpha}$ and its easy to check that this works- Firstly, if $x+y$ is neither of $p^{\alpha}$ or $p^{\alpha+1}$ then we anyway have that $f(f(x))$ is identity and $f(x+y)$ is identity so it works. Now, if $x+y=p^{\alpha+1}$ then neither of $x$ and $y$ are divisible by $p^{\alpha+1}$, so $gcd(f(f(x)),f(x+y))=gcd(f(f(x)),x+y)$. The other part follows the same way.

Pretty cool. The answer is every non-prime power, i.e. any number which cannot be written as $p^k$ for some prime $p$ and nonnegative integer $k$. I will provide a construction later, but first I will show some properties of Canadian functions. Denote the given assertion as $P(x,y)$. Property 1: For all $x$, $x \mid f(f(x))$. Proof: From $P(x,x)$, $\gcd(f(f(x)),f(2x))=x$, so $x \mid f(f(x))$ as desired. Property 2: For all $x$ and $k>1$, $x \mid f(kx)$. Proof: From $P(x,(k-1)x)$, $\gcd(f(f(x)),f(kx))=x$, so $x \mid f(kx)$ as desired. Property 3: If $x$ has at least two prime divisors, then $x \mid f(x)$. Proof: Let $p$ be a prime dividing $x$, and let $e=v_p(x)$. Also let $x'=x/p^e$. Since $p^e,x'>1$, by property 2: $$x' \mid f(p^ex') \implies x' \mid f(x) \text{ and } p^e \mid f(p^ex') \implies p^e \mid f(x).$$Since $\gcd(p^e,x')=1$ it follows that $p^ex'=x \mid f(x)$, as desired. Property 4: $x=f(f(x))$ for all $x$. Proof: Fix $x$ as an arbitrary positive integer, and let $f(f(x))=kx$, where $k$ is a positive integer (this is legal by property 1). Assume FTSOC that $k>1$, and note that $kx \mid f(k^2x)$ by property 2. Then, by $P(x,(k^2-1)x)$: $$\gcd(f(f(x)),f(k^2x))=\gcd(x,(k^2-1)x)=x,$$but since $kx \mid f(k^2x)$ and $kx \mid f(f(x))$ and $k>1$, this is impossible. Hence $f(f(x))=x$, as desired. Now using property 4 assertion rewrites as: $$\gcd(x,f(x+y))=\gcd(x,y).$$Using the Euclidean Algorithm, $\gcd(x,y)=\gcd(x,x+y)$. Then substituting $y$ for $x+y$, the equation becomes: $$\gcd(x,f(y))=\gcd(x,y) \qquad \text{for all } y>x.$$Fix $y$, and suppose $y$ has at least two prime divisors, so it is not a prime divisor. Then by property 2, $y \mid f(y)$, so write $f(y)=ky$. Assume FTSOC that $k \neq 1$ By property $4$, it follows that $f(ky)=y$. But since $ky$ has at least two prime divisors, it follows that: $$ky \mid f(ky) \implies ky \mid y \implies k \mid 1,$$which is absurd. Thus $k=1$, so $f(y)=y$ for all $y$ which are not prime powers. It remains to provide a construction showing that there exists a Canadian function $f$ such that $f(p^k) \neq p^k$ for arbitrary primes $p$ and nonnegative integers $k$. I claim that the function: $$f(n)=\begin{cases} p^{k+1} \text{ if } n=p^k\\ p^k \text{ if } n=p^{k+1}\\ n \text{ otherwise} \end{cases}$$works. Note that this function trivially satisfies $\gcd(x,f(y))=\gcd(x,y)$ if $y \not \in \{p^k,p^{k+1}\}$. $y=p^k$ produces the following equation: $$\gcd(x,p^k)=\gcd(x,p^{k+1}) \qquad \text{for all } x<p^k,$$while $y=p^{k+1}$ produces the equation: $$\gcd(x,p^k)=\gcd(x,p^{k+1}) \qquad \text{for all } x<p^{k+1}.$$But this is true, since for $\gcd(x,p^k) \neq \gcd(x,p^{k+1})$ to hold, $x$ must be a multiple of $p^{k+1}$, which is impossible due to size reasons. $\blacksquare$

As $\text{gcd}(x,y) = \text{gcd}(x,x+y)$, the condition is equivalent to $\text{gcd}(f(f(x)),f(y)) = \text{gcd}(x,y)$ for positive integers $x < y$. Call this $P(x,y)$. Claim: $f(f(x)) = x$ for all $x$. Proof: First, $P(x,2x)\implies x | f(f(x))$. Now suppose for some $x$ that $f(f(x)) = dx$ for a positive integer $d > 1$. Then $P(x,2dx)\implies \text{gcd}(dx,f(2dx)) = x$ while $P(dx,2dx)\implies dx | f(2dx)$, a contradiction and the claim is proved. Now note that $P(x,y)$ simplifies to $\text{gcd}(x,f(y)) = \text{gcd}(x,y)$. Claim: If $x$ is not a prime power then $f(x) = x$. Proof: Let $p$ and $q$ be distinct prime factors of $x$. Then $P\left(\frac{x}{p},x\right)$ and $P\left(\frac{x}{q},x\right)$ together imply that $x | f(x)$. But this means $f(x)$ is also not a prime power, so the same argument gives $f(x) | f(f(x))$. Then $x | f(x) | f(f(x)) = x$, so $f(x) = x$, as desired. Finally, let $p^k$ be a prime power (possibly $1$). Then it is easy to verify that the function defined by $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}$ is Canadian. Hence, the answer is all positive integers that are not prime powers.

Let $P(x, y)$ denote the assertion for given FE. For any positive integral $n>1$, $P(x, (n-1)x)\implies \text{min}\{\nu_p(f(f(x))), \nu_p(f(nx))\}=\nu_p(x)$ and hence, $x\vert f(nx)$ and $x\vert f(f(x))$. Thus, choosing $x$ with at least two prime divisors, for any prime divisor of $p$, we get $p^{v_p(x)} \vert f(p^{v_p(x)} \cdot \frac{x}{p^{v_p(x)}})\implies p^{v_p(x)}\vert f(x)\implies x\vert f(x)$. Now, $P(x, f(x)-x)\implies \nu_p(f(f(x)))=\text{min}\{\nu_p(x), \nu_p(f(x)-x)\}=\text{min}\{\nu_p(x), \nu_p(f(x))\}=\nu_p(x)$. Thus, $f(f(x))=x$ for all positive integral $x$. Also, $x\vert f(x)\vert f(f(x))\implies f(x)=x$. The above set up is for non prime power $x$. Now, We may claim that for any prime power $f$ is Canadian iff $f(p^k)=p^{k-1}$ and $f(p^{k-1})=p^k$ which would be true as it doesn't create any size issues.

Let $P(x,y)$ be the given assertion. Claim 1: $f(f(x))=x.$ Proof. We get $x\mid f(f(x))$ from $P(x,x)$ and we get $f(f(x))\mid x$ from $P(x,2f(f(x))-x).$ $\blacksquare$ Claim 2: Let $p^n\mid x\neq p^n,$ then $f(x)=x.$ Proof. Let $x=p^n \cdot m$ with $m$ prime and $\gcd(p^n,m)=1.$ From $P(m,x-m)$ we get $m\mid f(x)$ and from $P(p^n,x-p^n)$ we get $p^n\mid f(x).$ So $x\mid f(x).$ By the same argument, $f(x)\mid f(f(x)).$ The claim follows. $\blacksquare$ It is easy to verify that the following construction for Canadian functions works: $$f(x)=\begin{cases} x &\text{if } x\neq p^{k+1},p^k \\ p^{k+1} &\text{if }x=p^k \\ p^k &\text{if }x=p^{k+1}\end{cases}$$

Nice one! Answer is all $m$ except prime powers. Call $m$ 'good' if $f(m)=m$ for all of the Canadian functions $f$, and 'bad' otherwise. Let $P(x,y)$ be the assertion in given equation. Claim 1 : $f(f(x))=x$ and $x \mid f(kx)$ for any $k \in \mathbb{N}_{\ge 2}$. Proof : For $x=1$; if $f(1)>1$, consider $P(1,f(1)-1) \implies f(f(1))=1$; and if $f(1)=1$, still $f(f(1))=1$. Hence $f(f(1))=1$ and $1 \mid f(k) $ is clearly true. Let $x>1$, and let $k\in \mathbb{N}_{\ge 2}$. $P(x, (k-1)x)$ : gcd$(f(f(x)), f(kx))=x$. This directly implies $x \mid f(kx)$. We also have $x \mid f(f(x))$. Assume possible FTSOC $\frac{f(f(x))}{x} >1$, and let $p \mid \frac{f(f(x))}{x}$. Let $l$ such that $p^l \nmid x$ and $k=p^l$. As $x>1$, $p^l \mid f(p^lx) \implies p \mid \frac{f(p^lx)}{x}$. Hence $p \mid \frac{f(f(x))}{x}$ and $p \mid \frac{f(p^lx)}{x}$, contradicting gcd$\left(\frac{f(f(x))}{x}, \frac{f(kx}{x}\right)=1$. Hence our assumption was wrong and we get $f(f(x))=x$. This finishes claim 1. $\square$ Claim 2 : All prime powers are bad and rest are good. Proof : Firstly for non prime powers $x$, we can write them as $x=mn$ where $m,n \in \mathbb{N}_{\ge 2}$ and gcd$(m,n)=1$. By last claim , $m \mid f(nm)$ and $n \mid f(mn)$. Hence $x \mid f(x)$. Hence $f(x)$ is also non prime power and hence, $f(x) \mid f(f(x))$. Hence $x \mid f(x) \mid f(f(x))$. As $f(f(x))=x$, this forces $f(x)=x$, and this proves all non prime powers good. For prime powers, let $p$ be any prime and $N \in \mathbb{N}_0$. Consider $f$ such that : $f(p^N)=p^{N+1}$, $f(p^{N+1})=f(p^N)$ and $f(x)=x$ for all $x \neq p^N, p^{N+1}$. It can easily checked that this works. If $x+y \neq p^N, p^{N+1}$, $P(x,y)$ reads gcd$(x,x+y)=$gcd$(x,y)$, which is true. If $x+y=p^N$, $P(x,y)$ reads gcd$(x,p^{N+1})=$gcd$(x,y)=$gcd$(x,p^N)$. This is true because $x<p^N$. If $x+y=p^{N+1}$, $P(x,y)$ reads gcd$(x,p^{N})=$gcd$(x,y)=$gcd$(x,p^{N+1})$. This is true because $x<p^{N+1}$. Hence all prime powers are bad, finishing claim 2 $\square$ and we are done!

All these solutions seem to have the answer already then proceed to prove that answer. But I'm a bit confused on how you think of testing numbers based on their prime factors in the first place? Can someone explain how to approach this problem intuitively please? Thanks

embeak3746 wrote: All these solutions seem to have the answer already then proceed to prove that answer. But I'm a bit confused on how you think of testing numbers based on their prime factors in the first place? Can someone explain how to approach this problem intuitively please? Thanks I haven't done the problem, but from personal experience I can tell you that likely no one came up with the answer first, but discovered it through playing around with the probelm statement. But when writing up solutions, it is good practice to put the answer at the beginning, in order for the grader to immediatly see if you solved the problem or for people on AOPS who have also tried the problem to quickly see whether their answer is correct.

Solved with Interloop We claim that all non prime powers is the answer. Note that taking $y = x$, we see that $x$ divides $f(f(x))$. Next, note that for $a > x$ the statements $x \mid a$ and $x \mid f(a)$ are equivalent by taking $y = a-x$. Now note that for non prime powers $n$, let us take $p$ and $q$ to be two of its prime divisors, then note that $\frac{n}{p}$ and $\frac{n}{q}$ both divide $f(n)$ so $n$ divides $f(n)$. Next, if $f(f(n)) = tn$ for some $t > 1$, then take $x = n$ and $y = (t-1)n$ and we get a contradiction. So, $f$ is an involution. But then for non prime powers, we had that $n$ divides $f(n)$ which divides $f(f(n))$ thus $n = f(n) = f(f(n))$ for non prime powers. Next to give a construction (or as interloop calls them, constradiction) showing that prime powers fail, fix a prime $p$ and take $f(p^a) = p^{a+1}$ if $a$ is even and $f(p^a) = p^{a-1}$ if $a$ is odd. It is easy to see that this function is involutive so we can replace $f(f(x))$ with $x$. Next, if $x+y$ is not a prime power, we are anyways done. If it is, then by looking at the right the $\gcd$ can only be a power of $p$, and we can compare the prime powers on both sides and check they are equal (obviously $\nu_p(x) \leq \nu_p(x+y), \nu_p(f(x+y)$). As for all others, since we have already compared powers of $p$ on both sides, we can either divide or multiply $f(x+y)$ by $p$ depending on whether its a perfect square or not, and accordingly get $\gcd(x, x+y)$ on the left and thus we are done.

Notice the function equation is equivlent to (by letting $b = x+y$) \[\gcd(f(f(a)),f(b)) = \gcd(a,b) \text{ } \forall \text{ } a<b\]Thus any proper divisor of $b$ must divide $f(b)$. If $b$ isn't a prime power, then by choosing $a = \frac{b}{p_i} \mid f(b)$ (over all prime $p_i \mid b$) shows that $b \mid f(b)$. If $b$ isn't a prime power, plug in $a = b$ to get \[\gcd(f(f(b)),f(b)) = b \implies f(b) = b\]since $b \mid f(b) \implies f(b) \mid f(f(b))$. Now, Claim: The answer is all $m$ that aren't prime powers (including $1$). Proof: We've just shown these such $m$ work. Now, take \[f(x) = \begin{cases} p^{\ell-1} & x = p^\ell \\ p^{\ell} & x = p^{\ell-1} \\ x & \text{else}. \end{cases}\]It's not hard to check this satisfies the given FE. Now this shows that $f(p^{\ell-1}) \neq p^{\ell}$. Thus iterating over all primes $p$ and all $\ell \ge 1$ finishes. $\square$

The answer is everything except $p^k$ for some prime $p$ and nonnegative integer $k$. Given such $p$ and $k$, we will construct a Canadian function where $p^k$ isn't a fixed point. In fact, the desired function is \[f(x)=\begin{cases}p^{k+1}&x=p^k\\p^k&x=p^{k+1}\\x&\text{otherwise}\end{cases}.\]To show that this works, note that $f$ is an involution, so we just need to prove that \[\gcd(x,f(x+y))=\gcd(x,y).\]If $x+y\not\in\{p^k,p^{k+1}\}$, we already won. Otherwise, let $x=dm$ and $y=dn$ where $d=\gcd(x,y)$. If $x+y=p^k$, then note that $p^k\nmid x$ so we don't really care that it's $p^{k+1}$ and not $p^k$. If $x+y=p^{k+1}$, then still note that $p^{k+1}\nmid x$, so we still don't really care. Thus we have shown our construction. $P(x,x)$ gives $x\mid f(f(x))$. Thus the given equation implies \[\gcd(x,f(x+y))=\gcd(x,y).\]If $y=mx$ for a positive integer $m$, then \[x\mid f((m+1)x).\]Thus $f(n)$ is divisible by every proper divisor of $n$ for all $n$. If $n$ is not a prime or prime power, this is enough to imply that $n\mid f(n)$. Now suppose that there exists some $m$ such that $m<f(m)$. Then $P(m,f(m)-m)$ gives \[f(f(m))=m.\]Therefore, $f(m)$ maps to something less than $f(m)$, meaning that $f(m)$ is a prime power, say $p^k$. But even then, that means $m=f(f(m))$ is divisible by $p^{k-1}$. Since $m<f(m)$, we then have $m=ap^{k-1}$ where $a<p$. If $a\ne 1$, then we would get $m\mid f(m)$, impossible, so $a=1$, so $m$ is a prime power(or prime, or $1$) itself. Thus everything except $p^k$ for some prime $p$ and nonnegative integer $k$ is a fixed point. $\blacksquare$

Put in $y$ such that $x \mid y$, and we get that $x = \gcd(f(f(x)), f(x + y)) \implies x \mid f(f(x)), x \mid f(kx)$ where $k \geq 2$. Let $f(f(x)) = mx$. For the sake of contradiction, assume $m \neq 1$ for some $x$. Note that $2x \mid f(2mx) \implies f(2mx) \geq 2x \implies f(2mx) - x$ is positive. So, take $y = f(2mx) - x$. $$\gcd(mx, f(f(2mx))) = gcd(x, f(2mx))$$$2x \mid f(2mx) \implies x \mid f(2mx)$, so $\gcd(mx, f(f(2mx))) = x$. Also, $2mx \mid f(f(2mx))$, which means $mx \mid f(f(2mx)) \implies mx = x \implies m = 1$, a contradiction. So, $f(f(x)) = x$ for all $x$. $\gcd(x, f(x + y)) = gcd(x, y)$. We claim $m \mid f(m)$ if $m$ is not a prime power. Let $m = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$. Substitute in $x = \frac{m}{p_1^{\alpha_1}}$, $y = m - x$. This gives $\frac{m}{p_1^{\alpha_1}} \mid f(m)$, and repeat this taking $x = \frac{m}{p_k^{\alpha_k}}$, $y = m - x$, which gives $\frac{m}{p_k^{\alpha_k}} \mid f(m)$, and combining this with the earlier condition, we see that $m \mid f(m)$, so $f(m)$ is not a prime power as well. Hence, $m \mid f(m) \mid f(f(m)) = m \implies f(m) = m$ for $m$ not a prime power. For prime powers; pick $f(p^{2k + 1}) = p^{2k + 2}, f(p^{2k + 2}) = p^{2k + 1}$, which can be easily checked to work, so our answer is all numbers barring prime powers.

My solution is a bit different. Reduce the given equation to $(f(f(x)),f(z)) = (x,z)$ for $x<z$. Claim: $f(f(x))=x$ Case 1: $f(x)>x$, then we can always replace $z$ with $f(x)$, this gives that $f(f(x))$ divides both$x$ and $f(x)$, but putting $z=2x$ gives $x | f(f(x))$, this gives us $f(f(x)=x$ and $x | f(x)$. Case 2: $f(x)<x$, this guarantees that we can always take $x=f(z)$, as $x| f(f(x))$, we get the $gcd(f(f(x)),x) = x$, giving $f(z)$ divides $z$. Now, we have a few conclusions from both cases, first we take $z=f(f(x))$, $x < f(f(x)$ this is possible $f(x)<x$, and $f(f(x))$ isn't equal to $x$. This gives us $gcd(f(f(x)),f(f(f(x)))) = (x,ff(x))$. In case 2, we see that $f(x) \leq f(f(x)$ this means that for the not equality case (equality gives our claim directly), we apply case 1 to get that $f(x)=f(f(f(x)))$, so we get $f(x)=f^3(x)$ for all $x$. Replace it $f^3(x)$ to get that $gcd(f(f(x)),f(x)) = (x,ff(x))$, then as $f(x) | x| f(f(x))$, $f(x) = (x,ff(x))=x$, implying that $f(x)=x$ but our inequality was strict, so $z$ can not be equal to $f(f(x)$ ever, this means that $f(f(x)=x$. Now, our equation is reduced to $gcd(x,f(z)) = gcd(x,z)$. Assume, that $z$ = ${p_1}^{a_1}{p_2}^{a_2}...{p_k}^{a_k}$, then as $x<z$ for $z$ not equal to some $p^b$, we can always take $x$ as ${p_i}^{a_i}$ and get that ${p_i}^{a_i} | {p_1}^{a_1}{p_2}^{a_2}...{p_k}^{a_k}$ for all $0<i \leq k$. This means that $z | f(z)$ for all $z$ not a prime power. Now, we rewrite as $gcd(x,zk) = gcd(x,z)$ for non prime powers $z$. Let for a prime dividing $k$, ${v_p}(k) = c,{v_p}(z)=d,x=p^{d+1}$ for $x<z$, this implies that $p^{d+1} | z$, but this is not possible so $x \geq z$, this means that $p^{d+1} \geq p^{c+d}f_{1}f_{2}(k=p^c.f_1,z=p^d.f_2)$, $c$ has to be atleast 1, as a prime divides it($k \neq 1$), this means $f_1=f_2=1$ which is a contradiction as we assumed them to be not prime powers. To finish off, we take that for $p^a$ and $a$ odd, we get $f(p^a)=p^{a+1}$ and for even case, $f$ subtracts a power, also it is easily visible that $f(1)=1$. So, all non prime powers are possible as $f(m) = m$.