EDIT: Thanks for pointing that out, @TheUltimate123 !

Excellent problem! Solved with nukelauncher. Let \(P(x,y)\) denote the assertion. The answers are \(f(x)=x\) for all \(x\); \(f(x)=1\) for all \(x\ge2\); \(f(x)\equiv x\pmod2\) for all \(x\), and \(f(x)\in\{1,2\}\) for \(x\ge2\). Claim: \(f\) is either injective or bounded Proof. If \(f(a)=f(b)\) but \(a<b\), then by \(P(a,y)\) and \(P(b,y)\) we know \(f(y+f(a))\) divides both \(a+f(y)\) and \(b+f(y)\); hence it divides \(b-a\). It follows that \(f(y+f(a))\le b-a\), so \(f\) is bounded. \(\blacksquare\) \bigskip Proof for \(f\) injective: This case collapses after proving \(f(1)=1\). Let \(a=f(1)\) be larger than 1 for contradiction. Claim: \(f(x+a)=f(x)+1\) for all \(x\) Proof. By \(P(1,x)\), \(f(x+a)\le f(x)+1\). Evidently \(f(x+a)\ne f(x)\) by injectivity. If instead \(f(x+a)<f(x)\), we will show via induction on \(n\) that \(f(x+na)<f(x)\). If \(f(x+na)<f(x)\) then by \(P(1,x+na)\), \(f(x+(n+1)a)\le f(x+na)+1\le f(x)\), but by injectivity \(f(x+(n+1)a)\ne f(x)\), so the inductive step follows. But \(f(x+na)<f(x)\) contradicts injectivity, as desired. \(\blacksquare\) Now \(f(x+na)=f(x)+n\) for all \(x\), \(n\). Then \(f(1+f(2)a)=f(1)+f(2)=f(2+f(1)a)\), so \(1+f(2)a=2+f(1)a\) so \(a=1\). Finally I claim by induction that \(f(n)=n\) for all \(n\). If \(f(i)=i\) for all \(i\le n\), then from \(P(1,n)\), \[f(n+1)\le f(n)+1=n+1.\]But by injectivity \(f(n+1)\notin\{1,\ldots,n\}\), so \(f(n+1)=n+1\), completing the induction. \bigskip Proof for \(f\) bounded: Recall from the proof of the claim that if \(f(a)=f(b)\) then \(f(y+f(a))\mid b-a\) for all \(y\). Call this property \((*)\). Claim: \(f(x)\in\{1,2\}\) for \(x\ge3\). Proof. Over \(t\ge2\), let \(f(t)\) be maximal. Then for \(p\ge\max f\), by \(P(p-f(t-1),t-1)\) we have \(f(f(p-f(t-1))+t-1)=1\). then by \((*)\), for primes \(p,q\ge\max f\), \[f(t)\mid f(q-f(t-1))-f(p-f(t-1)).\]But \(f(t)\) is larger than both terms on the right, so \(f(p-f(t-1))=f(q-f(t-1))\). It follows that \(f(p-f(t-1))\) is constant over all prime \(p\ge\max f\); let this constant value be \(C\). Then by \((*)\) again, \[f(y+C)\mid q-p.\]Then for each odd prime \(r\), we can select \(p\), \(q\) with \(r\nmid q-p\) by Dirichlet, so \(f(y+C)\in\{1,2\}\). In particular, \(C\le2\), so \(f(x)\in\{1,2\}\) for \(x\ge3\). \(\blacksquare\) Now we examine two cases: If \(f(x)=1\) for \(x\ge3\), then by \(P(a,1)\) for \(a\ge3\), \(f(2)\mid a+f(1)\), so \(f(2)=1\). Otherwise, assume \(f(x)=2\) for some \(x\ge3\). If for \(a,b\ge3\), \(f(a)=f(b)\) but \(b-a\) is odd, then by \((*)\), \(f(y+f(a))\mid b-a\), so \(f(y+f(a))=1\) for all \(y\), contradiction. If \(f(3)=f(5)=\cdots=2\) and \(f(4)=f(6)=\cdots=1\) then by \(P(3,3)\), \(2\mid5\), absurd. Thus \(f(3)=f(5)=\cdots=1\) and \(f(4)=f(6)=\cdots=2\). By \(P(1,4)\), \(f(f(1)+4)\mid3\), so \(f(1)\) is odd. For odd \(a\ge3\), by \(P(a,1)\), we have \(f(2)\mid a+f(1)\), so \(f(2)\mid2\). But by \(P(2,3)\), \(f(f(2)+3)\mid3\), so \(f(2)\) is even. In both cases, we are done.

My solution during the contest which uses the bounded gaps between prime numbers. The answer is $f(x)=x$, $$f(x)=\begin{cases}\text{arbitrary}&\text{if } x=1\\ 1&\text{if } x\geq 2\end{cases}$$and $$f(x)=\begin{cases}\text{arbitrary}&\text{if } x=1\\ 1&\text{if } x \text{ is odd and greater than 1 }\\2&\text{if } x\text{ is even }\end{cases}$$It is straightforward to show that all three classes of function satisfies the divisibility, we now show that they are the only ones. We will divide into two cases: Case I: $f$ is bounded. Suppose $f\leq M$. We will use the fact that there exists infinitely many pairs of primes $(p,q)$ such that $0<p-q\leq 246$ Define $$S=\{(a,b):f(a)=f(b):a>b\}$$$$D=\{a-b:(a,b)\in S\}$$Let $m=\min{D}$. CLAIM 1. If $n>M$ then $$f(n)\leq m$$Proof. Since $m\in D$ suppose $m=a-b$. Then for any positive integer $y$, \begin{align*} f(f(a)+y)&|a+f(y)\\ f(f(b)+y)&|b+f(y)\\ \end{align*}Hence $f(f(a)+y)|a-b$ and therefore, for all $n>M$ we have $n-f(a)>0$, hence $$f(n)=f(f(a)+(n-f(a)))\leq a-b=m$$$\blacksquare$ CLAIM 2. There exists infinitely many integers $a$ such that $$f(a)=1$$Proof. Pick a sufficiently large prime $p$ with $p>2M$, then $$f(f(p-f(y))+y)|p$$For all integers $y$. Notice that left hand side is at most $M$, hence we must have $$f(f(p-f(y))+y)=1$$Therefore, it suffices to take $a=f(p-f(y))+y$, since $y$ is arbitrary we are done. $\blacksquare$ CLAIM 3. $m\leq 246$ Proof. Pick two sufficiently large primes $p,q$ such that $0<p-q<246$, then similar to the way in claim 2 we must have $$f(f(p-f(y))+y)=1=f(f(q-f(y))+y)$$Now suppose on the contrary that $f(p-f(y))\neq f(q-f(y))$, then $(f(p-f(y))+y,f(q-f(y))+y)\in S$, meanwhile, there difference $$|f(p-f(y))-f(q-f(y))|$$is less than $m$ since each of them is at most $m$ from Claim 1. This contradicts the minimality of $m$. Therefore, $$f(p-f(y))=f(q-f(y))$$Hence $m\leq p-f(y)-(q-f(y))=p-q\leq 246$. $\blacksquare$ CLAIM 4. If $n> 246$ then $f(n)\leq 246$. Proof. Take the same $p,q$ as in Claim 3. Let $x_1=p-f(y)$, $x_2=q-f(y)$. Then from the proof of Claim 3 we have $f(x_1)=f(x_2)$. Therefore, \begin{align*} f(f(x_1)+y)&|x_1+f(y)\\ f(f(x_2)+y)&|x_2+f(y)\\ \end{align*}This implies $f(f(x_1)+y)|x_1-x_2\leq 246$, since $f(x_1)\leq m\leq 246$ by Claim 1 and Claim 3 we are done. $\blacksquare$ Corollary 1. Define $$S_1=\{(a,b):f(a)=f(b):a>b>246\}$$$$D_1=\{a-b:(a,b)\in S_1\}$$Let $m_1=\min D_1$, then if $n>246$ we have $$f(n)\leq m_1$$Proof. Similar to Claim 1, let $m_1=a-b$. Then for any positive integer $y$, \begin{align*} f(f(a)+y)&|a+f(y)\\ f(f(b)+y)&|b+f(y)\\ \end{align*}Hence $f(f(a)+y)|a-b$. From Claim 4 we have $f(a)\leq246$, therefore, for all $n>246$ we have $n-f(a)>0$, hence $$f(n)=f(f(a)+(n-f(a)))\leq a-b=m_1$$ Corollary 2. $m\leq 2$. Proof. Notice that $269,271$ is a pair of twin prime. From Claim 2 we can pick arbitrary large integer $a$ such that $f(a)=1$. Then we have $$f(f(269-f(a))+a)|269$$Since $f(269-f(a))+a\geq 246$, by Claim 4, $f(f(269-f(a))+a)<246$, hence it can only be $1$, that is $$f(f(268)+a)=f(f(269-f(a))+a)=1$$Similarly $$f(f(270)+a)=f(f(271-f(a))+a)=1$$Now if $f(268)\neq f(270)$ then $$(f(268)+a,f(270)+a)\in S_1$$hence $$|f(270)-f(268)|\in D_1$$However, from Corollary $1$ each of them is at most $m_1$, therefore $$|f(270)-f(268)|<m_1$$This contradicts the minimality of $m_1$, Therefore we must have $f(268)=f(270)$, which implies $(268,270)\in S$. hence $m\leq 2$. Now either $m=1$ or $m=2$, in both case it is easy (using the same method as in Claim 1) to show that the only solutions are the second and third one as claimed. Case II: f is unbounded. Notice that $f$ is injective, otherwise from Claim 1 we have $f$ is bounded, contradiction. Let $f(1)=c$, then $$f(y+c)|1+f(y)$$hence $$f(y+c)\leq 1+f(y)$$Using induction we have $$f(ac+b)\leq a+f(b)$$Define $$M=\max\{f(1),f(2),...,f(c)\}$$Now for a fixed natural number $d$ and all $x\leq cd$, $x=ac+b$ where $a\leq d-1$ and $1\leq b\leq c$ Hence $$f(x)\leq a+f(b)\leq d-1+M$$However, from injectivity we have that $$f(1),f(2),...,f(cd)$$are all distinct numbers, therefore, $$cd\leq d-1+M$$This can't hold for large $d$ if $c>1$. Therefore $c=1$, as a result, $$f(y+1)\leq 1+f(y)$$Hence $f(y)=y$ by injectivity.

For the bounded case, here is a completely elementary solution (I am pretty sure dirichlet and bounded gaps are not elementary, but bounded gaps may be proven with elementary methods, for example, $(2n)^{\pi(2n)}>\binom{2n}{n}>2^n$.) Let $d_m$ be the minimal number such that there exists $x$ such that $f(x)=f(x+d_m)$ Then $P(x,y), P(x+d_m,y)$ yields $f(f(x)+y)\mid d_m$ for all $y\in \mathbb{Z}^+$ (1). Then consider $f(f(x)),f(f(x)+1),\cdots,f(f(x)+\tau(d_m))$. Two of them must be equal because there are $\tau(d_m)+1$ terms but $\tau(d_m)$ options for these terms, so it follows $d_m\le \tau(d_m)$, which implies $d_m\in \{1,2\}$. Subcase 1: $d_m=1$. Comparing $P(l,y), P(l+1,y)$ yields $f(y)=1\forall y\ge 2$. There are no restrictions on $f(1)$. Subcase 2: $d_m=2$. We can see for some $l$, $f(l+2q)=1\forall q\ge 0, f(l+2q+1)=2\forall q\ge 0$. This is true because $f(x)\ne f(x+1)$ for any $x$. I claim $l$ is odd. If $l$ is even, $f(l)+l$ is odd but $f(f(l)+l)$ is even so $P(l,l)$ gives a contradiction. Comparing $P(l,y), P(l+2,y)$ yields $f(f(l)+y)\mid 2$. Pick $f(l)=1$, so we can see $f(y)=\gcd(2,y)\forall y\ge 2$.

I have a question. At my solution, I thought that If there are infinite positive integers there is a gcd. Is it correct?

Anybody?

Mop2018 wrote: Anybody? Please don't bump so quickly. Towards your question: Of course for any set of positive integers, there is a greatest common divisor, just the maximal number dividing all of them. For example, the gcd of the set of all positive integers is just $1$.

Thanks. I was quick. sorry for that

Let $P(x,y)$ denote the original proposition. We split the problem into two cases: Case I: $f$ is unbounded. In this case, we get that $f$ is injective. Indeed if $f(x_1)=f(x_2)$ then comparing $P(x_1,y)$ and $P(x_2,y)$ gives us $f(f(x_1)+y) \mid x_1-x_2$ which gives $x_1=x_2$ since $f$ is unbounded. Let $f(1)=k$. $P(1,x)$ gives $f(x+k) \mid f(x)+1$ $$\implies f(x+k) \leq f(x)+1$$Call the above $Q(x)$. Now if $f(a)<f(b)$ for some $a>b$ then $Q(a)$ $\implies$ $f(a+k) \leq f(a)+1 \leq f(b)$ $\implies$ $f(a+k)<f(b)$ by injectivity $\implies$ $f(a+nk) < f(b)$ for all positive integers $n$, which contradicts injectivity. Therefore $f$ is non-decreasing, in fact strictly increasing due to injectivity. Hence $Q(x)$ gives $f(x+k) = f(x)+1$ for all $x$. If $k>1$ get $$f(x) < f(x+k-1) < f(x+k) =f(x)+1$$Contradiction! So $k=1$, and by easy induction we get the solution $$\boxed{f(x)=x \ \ \forall x \in \mathbb{N}}$$ Case II: $f$ is bounded. Let $M= \limsup\limits_{t \rightarrow \infty} f(t)$. Claim: $f(x_1)=f(x_2)$ $\implies$ $M \mid x_1-x_2$ Proof: Follows from comparing $P(x_1,y)$ and $P(x_2,y)$ for a $y$ such that $f(f(x_1)+y)=M$. $\blacksquare$ If $M=1$ then $f(x)=1$ for all large $x$. Comparing $P(x,y)$ and $P(x+1,y)$ for a large $x$ gives us $f(y+1)=1$ for all $y$. Hence we get the solution $$\boxed{f(x)=1 \ \text{for} \ x>1 \ \text{and} \ f(1) \ \text{arbitrary}}$$Now suppose $M \geq 3$. Let $n$ be a large positive integer such that $n \equiv -1 \pmod p$ for all primes $p \leq M$. Note that the only number not exceeding $M$ which divides either $n$ or $n+2$ is $1$. Therefore $P(n-f(x),x)$ and $P(n+2-f(x),x)$ for some large $x$ give $$f(f(n-f(x))+x)=f(f(n+2-f(x))+x)=1$$$$\implies M \mid f(n+2-f(x))-f(n-f(x))$$For large values, $f$ is bounded above by $M$, so the only way the above divisibility holds is $$f(n+2-f(x))=f(n-f(x))$$$\implies M \mid 2$, contradiction! Finally assume $M=2$. Therefore $f(x) \in \{ 1,2 \}$ for all large $x$ and by the claim, $f(x+1) \neq f(x)$ for all $x$. Hence for all large $x$, either $f(x)$ and $x$ have same parity, or opposite parity. In the second case, take $x,y$ to be large even integers; then $x+f(y)$ is odd while $f(f(x)+y)$ is even, contradiction! So $f(x) \equiv x \pmod 2$ for all large $x$. Now taking $t$ to be a large odd integer and comparing $P(t,y)$ and $P(t+2,y)$ we get $f(y+1) \mid 2$ $\implies$ $f(x) \leq 2$ for all $x>1$. So the previous paragraph in fact holds for all $x>1$. It is also easy to see that $f(1)$ must be odd (for instance from $P(2021,1)$). Therefore we get the solution $$\boxed{ f(x) = 2 + x -2 \left \lceil \frac{x}{2} \right \rceil \ \text{for} \ x>1 \ \text{and} \ f(1) \ \text{arbitrary but odd}}$$

We do it in two cases. $f$ is bounded and $f$ is unbounded. Let's handle the unbounded case first. Observe that if $f(a)=f(b)=k$ then we have $f(y+k)|a-b$ but now due to unboundedness of $f$, we have that $f$ is injective. Now, let $m$, be the smallest number in the range of $f$ and let $f(a_0)=m$. Now, we claim that if $a_i=a_0+if(1)$ then $f(a_i)=m+i$. We prove this by induction on the assertion $P(a_{i},1)$. Result is true for base case $i=0$ by our assumption. Observe that $f(a_0+if(1))=f(a_0+(i-1)f(1)+f(1))|1+f(a_0+(i-1)f(1))=1+m+i-1=m+i\implies f(a_0+if(1))\le m+1$ but since $f$ is injective and does not take the values from $1$ to $m-1$ and $f(a_0),\cdots f(a_{i-1})$ takes the value $m,m+1,\cdots m+i-1$, we have $f(a_0+if(1))=m+i$. But, now if $f(1)\ne 1$ then we have that $f(a_0+1)$ cannot take any value which is absurd. Now, if $f(1)=1$, we have $m=a_0=1$ and thus $f(n)=n$. Now, if $f$ is bounded. This means that $f$ takes finitely many values. Let $S$ be the set of values which $f$ takes on infinitely often and $|S|=s$. Now, for all large enough $n$, $f$ only takes values in $S$. So, consider $f(n),f(n+1),\cdots f(n+s)$. By PHP, atleast $2$ of these take the same value and gap at most $s$. Let these values be $a,b$ then $f(f(a)+y)|a-b$ but $a-b$ is at most $s$ but we have that $f(f(a)+y)$ takes all $s$ values in $S$ so some number less than $s+1$ has atleast $s$ divisors. Thus, $a-b=s\in\{1,2\}$. If $s=1$, then we have $f(1+y)|1\implies f(y+1)=1$ and thus, all values except $1$ go to $1$. Observe that $f(1)=n, f(1+y)=1\forall y\ge 1$ works. Now, $s=2$, thus, $f(f(a)+y)|2$ and thus $f$ takes values $1,2$. Observe that two consecutive numbers must go to different values and all large enough values alternately go to $1,2$. But now consider when $f(a)=1$. Thus, $f(y+1)|2$. Thus, from $2$ itself values alternately go to $1,2$. If $f(2)=1$, then $(x,y)=(2,2)\implies f(1+2)|3\implies 2|3$ which is absurd. Thus, $f(2)=2$. Now, $(3,1)\implies f(2)|3+f(1)\implies 2|3+f(1)\implies f(1)\equiv 1 \pmod{2}$. But its easy to check $f(1)$ is odd and $f(n)\equiv n\pmod{2}$ and $f(n)\in \{1,2\}$. Thus, only these solutions work- $f(x)=x$ $f(x)=1 \forall x\ge 2$ $f(x)\equiv x\pmod{2} \forall x\ge 1$ and $f(x)\in \{1,2\}\forall x\ge 2$ and $f(1)$

Really nice problem! Solved with Pujnk Let $P(x,y)$ denote the given assertion. Consider two cases: Case 1: $f$ is unbounded Suppose $f(a) = f(b)$. $P(a,y)$ gives that $f(f(a)+y) | a + f(y)$ and $P(b,y)$ gives $f(f(b)+y) | a+f(y)$, this means $f(f(a)+y) | a-b$. Since $f$ is unbounded, the LHS takes on arbitrarily large values and so this is impossible unless $a-b = 0 \implies a=b$ and so $f$ is injective. Let $f(1) = c$. Now, $P(1,y)$ gives that $f(y+c) | f(y) + 1$. This means that $f(y+c) \le f(y) + 1$. Suppose for some $y$, we have $f(y+c) < f(y) + 1$, then since for every increase in $c$, the value of $f(y)$ increases by at most $1$, we can easily see that injectivity is contradicted. So, we have that $f(y+c) = f(y) + 1$ for all $y$ $P(p-f(y), y)$ gives that $f(f(p-f(y))+y) | p$ and so $f(f(p-f(y))+y) = 1$ or $p$ but since $f$ is injective, it can be equal to $1$ at most once, so we have that $f(f(p-f(y))+y) = p$. Also since $f$ is injective, we have that $f(p-f(y))+y$ is constant for all $y$, which gives that $f(p-f(y)) = p-y$ Now, $P(x,p-f(x))$ gives that $f(p) | p$ but since $f$ is injective, this forces $f(p) = p$ for all primes except at most $1$ Since we had $f(y+c) = f(y) + 1$, we get that $f(kc+1) = k+1$. But by dirichlet, we have infinitely many primes $p = kc + 1$ and so pick some such prime. We then have that $p = f(p) = f(kc+1) = k+1$ and so we get that $k = p-1 \implies k = kc-1 \implies c = 1$ and so $f(1)= 1$. So, we have that $f(k+1) = k+1$ for all $k \ge 1$ and so this means $f(n) = n$ for all $n \in \mathbb{N}$ is the only solution in this case Case 2: (The harder case) $f$ is bounded Let $S := \{n \mid f(n) = 1\}$. Observe that $P(p-f(y), y)$ gives that $f(f(p-f(y))+y) | p$ but since $f$ is bounded, this means for all sufficiently large primes $p$, we have that $f(f(p-f(y))+y) = 1$ and so $f(p-f(y))+y \in S$ for all big primes $p$ and all $y \in \mathbb{N}$, so this means there is at least $1$ element in $S$ Suppose $z \in S$, then $P(p-1, z)$ for some big enough prime gives that $f(z+f(p-1)) = 1$ and so $z + f(p-1) \in S$. In particular, this means that there are infinite elements in $S$ From $P(z,n)$ and $P(z+f(p-1),n)$, we get that $f(n+1) | f(p-1)$ for all big enough primes $p$. So suppose $f(p-1) < f(q-1)$ for big primes $p,q$, but then taking $n=q-2$, we get that $f(q-1) | f(p-1)$, which is impossible, so we get that $f(p-1)$ is constant for all big enough primes $p$. Since $f(\text{anything else})$ divides this, we know that $f(p-1)$ is also equal to the maximum value of $f$, call it $M$ But from the unbounded case, we have that if $f(a) = f(b)$, then $f(x+f(a)) | b-a$ for all $x$, so putting $a = p-1, b = q-1$, we get that $f(y+M) | q-p$. Now, for each odd prime that divides $f(y+M)$, we can find a $q$ such that $q - p \neq 0 \pmod r$. Then, by CRT, we combine these into one thing and we can still find a prime $q$ by dirichlet. So, we can ensure that $f(y+M)$ can only take on powers of two. But we can do better than this! Add to the conditions for selecting $q$, the fact that $q \equiv p+2 \pmod 4$ so that $v_2$ of the RHS becomes $2$. This forces $f(y+M) | 2$ and so for big enough numbers, $f$ is just $1$ and $2$. But since $f(p-1) = M$ for big enough $p$, we get that $M = 1$ or $2$ as well. So $f(x)$ only takes the values $1$ and $2$ for all $x \ge 3$ If $f(x) = 1$ for all $x \ge 3$, from $P(3,1)$, we get that $f(2) | n+f(1)$ for all $n$, which forces $f(2) = 1$. Then, $f(1)$ can be chosen arbitrarily because it doesnt really matter for the FE to work. So this is one solution, $f(1)$ arbitrary and $f(n) = 1$ for $n > 1$ Now suppose $f(x) = 2$ for some value $x \ge 3$. Then, we know that $f(p-1) = 2$ for all primes $\ge 3$. In particular, $p = 3$ gives that $f(2) = 2$. We know that if $f(a) = f(b)$, then $f(x+f(a)) | a-b$, we can pick some $x$ such that LHS becomes $2$ and so we have $2 | a-b$ and so we get that $f(x) = 2$ for any even $x$. We know that if $f(x) = 1$, then $f(x+f(p-1)) = 1$ and so we get $f(x+2) = 1$. So we get that all sufficiently large odd numbers map to $1$. Now, suppose $f(x) = 2$ where $x$ is an odd number $\ge 3$, then we get that all numbers greater than $x$ also map to $2$, which is impossible. So, we have that all even numbers map to $2$ and all odd numbers (except 1) map to $1$. Now, consider what the value of $c = f(1)$ can be. $P(x,1)$ gives that $f(f(x)+1) | x+c$. If $c$ is odd, then picking an even number $x$, we get that $2 | x+c$, which is impossible since $x+c$ is odd. So, $c$ must be even, and this obviously will work. So, finally, after all of that, the solutions are: 1. $f(x) = x$ for all $x \in \mathbb{N}$ 2. \[f(x) = \begin{cases} c & \text{if } x=1 \\ 1 & \text{if } x>1 \end{cases}\]for arbitrary $c$, and 3. \[f(x) = \begin{cases} 2c-1 & \text{if } x=1 \\ 1 & \text{if } x>1 \text{ is odd} \\ 2 & \text{if } x \text{ is even.} \end{cases}\]for arbitrary $c$ which finishes the problem.

When your first China MO solve is a P6 Ok time for the writeup. Find all functions $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$, such that for any $x,y \in \mathbb{Z}_+$,$$f(f(x)+y)\mid x+f(y).$$ The only solutions are \[\boxed{f(x)=x}\]\[\boxed{f(x)=\begin{cases} c & \text{ if }x=1 \\ 1 &\text{ if } x>1 \\ \end{cases}},\]where $c$ is any positive integer constant, and \[\boxed{f(x)=\begin{cases} d & \text{ if }x=1 \\ 1 & \text{ if } x>1 \text{ and }x \text{ is odd } \\ 2 & \text{ if }x \text{ is even } \\\end{cases}},\]where $d$ is any odd positive integer constant. First we will verify that they work. The first solution is trivial because $f(f(x)+y)=x+f(y)=x+y$. For the second solution, we note that $f(x)+y>1$, so $f(f(x)+y)=1$, and we are done because $1$ divides all positive integers. For the third solution, we note that $f(x)\equiv x\pmod 2$ and also $f(x)+y>1$. If $x+y$ is even, then $f(f(x)+y)$ is even, so it is $2$. Now, $x+f(y)$ is also even, so $2\mid x+f(y)$. If $x+y$ is odd, then $f(f(x)+y)$ is odd, so it is $1$. Now, $1$ divides every positive integer, so $1\mid x+f(y)$. Thus, all of these solutions work. We now prove they are the only ones. Let $P(x,y)$ denote the given assertion. We start with the following lemma: Lemma: $f$ is either injective or bounded above. Proof: Suppose FTSOC $f$ was not injective and unbounded. Let $a>b$ satisfy $f(a)=f(b)$. $P(a,x): f(f(a)+x)\mid a+f(x)$. $P(b,x): f(f(b)+x)\mid b+f(x)$, so $f(f(a)+x)\mid b+f(x)$. Now that $f(f(a)+x)$ divides both $a+f(x)$, and $b+f(x)$, it must divide \[\gcd(a+f(x),b+f(x)),\]which divides $a+f(x)-(b+f(x))=a-b$. So $f(f(a)+x)\le a-b$ for each positive integer $x$. If this were true, then $f$ would be bounded, a contradiction. $\blacksquare$ Now, we split into two cases, based on whether $f$ is injective or not. Case 1: $f$ is injective. Set $f(1)=c$. Claim 1.1: For each nonnegative integer $n$, $f(nc+1)\le n+c$. Proof: We prove the result by induction. Base cases: We will show that both $n=0$ and $n=1$ work. Clearly $n=0$ works since $f(1)=c$. $P(1,1): f(c+1)\mid c+1$, so $f(c+1)\le c+1$, so $n=1$ also works. Inductive step: We will show that if $f(nc+1)\le n+c$, then \[f((n+1)c+1)\le n+c+1\] $P(1,n): f(n+c)\mid f(n)+1$, so $f(n+c)\le f(n)+1$. This implies that \begin{align*} f((n+1)c+1) \\ =f(nc+1+c) \\ \le f(nc+1)+1 \\ \le n+c+1, \\ \end{align*}as desired. $\blacksquare$ Claim 1.2: For each positive integer $x>1$, $f(x)>c$. Proof: Clearly $f(x)\ne c$ as $f$ is injective. Suppose FTSOC $f(a)<c$ for some $a>1$. We will show that $f(a+nc)< c$ for each nonnegative integer $n$ by induction on $n$. Base cases: Clearly $n=0$ works. $P(1,a): f(a+c)\le f(a)+1<c+1$, so $f(a+c)\le c$. However, due to injectivity, $f(a+c)\ne c$, so $f(a+c)<c$. Inductive step: We will show that if $f(a+nc)<c$, then \[f(a+(n+1)c)<c\] $P(1,x): f(x+c)\le f(x)+1$. So \begin{align*} f(a+(n+1)c) \\ =f((a+nc)+c) \\ \le f(a+nc)+1 \\ < c+1 \\ \end{align*} However, since $f$ is injective, $f(a+(n+1)c)\ne c$, so \[f(a+(n+1)c)<c,\]as desired. Thus, $f(a+nc)<c$. Consider the set $\{f(a),f(a+c),\ldots, f(a+(c-1)c)\}$. Clearly every element in this set must be less than $c$. Now that there are $c$ elements, two of them must be equal, which contradicts injectivity. $\blacksquare$ Now let \[S_n=\{f(1),f(c+1),f(2c+1),\ldots,f(nc+1)\}\] Clearly each element in $S_n$ is in the interval $[c,n+c]$. There are $n+1$ elements in this interval, so $S_n$ takes on each value from $c$ to $n+c$. Thus, all $x\ge c$ are in the infinite set \[S=\{f(1),f(c+1),f(2c+1),\ldots,\}\] If $c>1$, then the set \[T=\{f(2),f(c+2),f(2c+2),\ldots,\}\]contains no elements in common with $S$. Since $f$ is injective, all elements in $T$ are less than $c$. However, this is a contradiction since all the elements of $T$ are distinct. This implies $c=1$. Now we prove $f(n)=n$ for each positive integer $n$ by induction on $n$. Base case: Clearly $f(1)=1$. Inductive step: Suppose $f(x)=x$ for all $x<n$. We will show $f(n)=n$. $P(n-1,1): f(n)\le n$. But if $f(n)=a<n$, then $f(n)=f(a)$, a contradiction. So $f(n)=n$, as desired. $\blacksquare$ Case 2: $f$ is not injective, and thus bounded. Since $f$ isn't injective, let $a>b$ satisfy $f(a)=f(b)$. Now similarly to our Lemma at the beginning, we find that $f(f(a)+x)\mid a-b$ for any positive integer $x$. Let $n$ denote the gcd of all possible values of $a-b$, where $a>b$, and $f(a)=f(b)$. Note that $f(k)\mid n$ for all sufficiently large $k$. Also, if $f(a+x)=f(a)$ for a positive integer $x$, then $x\ge n$. Call this fact 1 Let $M$ be some sufficiently large positive integer. Consider the set with $n$ elements $\{f(M),f(M+1),\ldots,f(M+n-1)\}$. By fact 1, all elements of this set must be distinct. However, since $M,M+1,\ldots,M+n-1$ are all sufficiently large, all elements of the set divide $n$. Thus, there are at least $n$ distinct divisors of $n$, which implies $n\in \{1,2\}$. Subcase 2.1: $n=1$. Then $f(k)=1$ for all sufficiently large $k$. We prove the following claim: Claim: 2.1.1: $f(x)=1$ for all positive integers $x>2$. Proof: Let $x>2$ be some positive integer greater than $1$ and $C$ be some sufficiently large positive integer. $P(C,x-1): f(x)\mid C+f(x-1)$. $P(C+1,x-1): f(x)\mid C+1+f(x-1)$. Thus, $f(x)\mid \gcd(C+f(x-1),C+1+f(x-1))=1$, so $f(x)=1$. $\blacksquare$ Now $f(1)$ can be any positive integer, so this gives the second solution $\boxed{f(x)=\begin{cases} c & \text{ if }x=1 \\ 1 &\text{ if } x>1 \\ \end{cases}}$. Subcase 2.2: $n=2$. Then $f(k)\in \{1,2\}$ for any sufficiently large $k$. Since $n=2$, $f(a)\ne f(a+1)$ for any $a$. Claim: 2.2.1: $f(x)\in \{1,2\}$ for all positive integers $x>1$. Proof: Let $x$ be a positive integer greater than $1$ and $M$ be a sufficiently large positive integer with $f(M)=1$. Note that $f(M+1)\ne f(M)$, so $f(M+1)=2$, and $f(M+2)\ne f(M+1)$, so $f(M+2)=1$. $P(M,x-1): f(x)\mid M+f(x-1)$. $P(M+2,x-1): f(x)\mid M+2+f(x-1)$. Thus, $f(x)\mid \gcd(M+f(x-1),M+2+f(x-1))\mid 2$, as desired. $\blacksquare$ For $m>1$, note that $f(m)\ne f(m+1)$, and $f(m+1)\ne f(m+2)$, so $f(m)=f(m+2)$. If $f(2)=1$, then $P(2,2): f(3)\mid 3$. However, $f(3)\ne f(2)$, so $f(3)=2$, a contradiction as $2\nmid 3$. Thus, $f(2)=2$. This implies $f(x)=2$ for all even $x$, and $f(x)=1$ for all odd $x>1$. To arrive at the solution $\boxed{f(x)=\begin{cases} d & \text{ if }x=1 \\ 1 & \text{ if } x>1 \text{ and }x \text{ is odd } \\ 2 & \text{ if }x \text{ is even } \\\end{cases}}$, we have to show $f(1)$ is odd. $P(1,3): f(f(1)+2)\mid 3$. If $f(1)$ was even, then $f(1)+2$ is even, so $f(f(1)+2)$ is even, a contradiction. $\blacksquare$

Denote the assertion by $P(x,y).$ If $f(u)=f(v)$ then $P(u,x)$ and $P(v,x)$ gives $f(f(u)+f(v)+x)$ $\mid u-v.$ So either $u=v$ or $f$ is bounded. If $f$ is injective, then $P(1,x)$ gives $f(x+f(1))$ $\mid f(x)+1.$ If $f(x+f(1))$ $<f(x).$ Then by induction, $f(x+kf(1))<f(x)$ a contradiction with injectivity. So $f(x+kf(1))=f(x)+k$ and by injectivity $f(1)=1.$ Now by induction $f$ is the identity, which works. If $f$ is bounded, then let $\gamma$ be the maximum of $f.$ So $u-v\leq \gamma.$ And thus $\tau (\gamma)\geq \gamma$ iff $\gamma=1,2.$ If $\gamma =1$ then $P(x,y)$ and $P(x+1,y)$ gives $f(x)=1$ for $x>1$ and this works. If $\gamma=2$ then it's not hard to get $2\mid f(x)-x$ and $f(x)=1,2$ for all $x>1.$ This works.

We prove that all such functions are $f(x)=x$ for all $x\in\mathbb{Z}_{>0}$, $$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\text{ is odd;}\\2\text{ if }x\text{ is even.}\end{cases}$$and $$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\ne1.\end{cases}.$$Let $P(x,y)$ be the proposition $f(f(x)+y)\mid x+f(y)$. We have that, if $f(a)=f(b)=c$: $$P(a,x): f(c+x)\mid a+f(x),$$$$P(b,x): f(c+x)\mid b+f(x)$$$$\implies f(c+x)\leq|a-b|,$$and we conclude that $f$ is injective or bounded. $\textbf{Case 1:}$ If $f$ is injective, let $x_0$ be such that $f(x_0)=m$ is minimun. $$P(1,x_0): f(f(1)+x_0)\mid1+f(x_0)\implies f(f(1)+x_0)\leq1+f(x_0).$$If $f(f(1)+x_0)<1+f(x_0)$, then $f(f(1)+x_0)=f(x_0)$, a contradiction since $f$ is injective. Therefore, we have $f(f(1)+x_0)=1+f(x_0)$. We prove by induction that $f(nf(1)+x_0)=n+f(x_0), n\in\mathbb{Z}_{\geq0}$. Suppose that for all $n_0\leq n$ we have the desired property. Then: $$P(1,nf(1)+x_0): f(f(1)+nf(1)+x_0)\mid 1+f(nf(1)+x_0)$$$$\implies f((n+1)f(1)+x_0)\leq n+1+f(x_0).$$If we don't have the inequality, we must have $f((n+1)f(1)+x_0)=f(x_0)+k=f(kf(1)+x_0)$, for some $k<n+1$, which implies $f(1)=0$ from $f$ injective, a contradiction. From this, since $x+f(x_0)$ goes through every element from $f$'s image, and since $f$ is injective, we must have that $nf(1)+x_0$ goes though every element of $\mathbb{Z}_{>0}$, from where we conclude that $f(1)=1=x_0$, and thus $f(x)=x$ for all $x\in\mathbb{Z}_{>0}$. $\textbf{Case 2:}$ If $f$ is bounded, see that if $C=min\{|a-b|\}$, where $f(a)=f(b)$, then $f(x)\mid C$, for all sufficiently large $x$. This implies that all elements from the set $A=\{f(x),f(x+1),\dots,f(x+C-1)\}$ are distinct. But, for $x>>0$ we have that all elements from $A$ divide $C$, and thus we conclude that $C\in\{1,2\}$ and, therefore, $f(x)\in\{1,2\}$ for $x>>0$. Suppose that we have $f(x)=2$ for some $x$ sufficiently large. Then: $$P(x,x-2): f(f(x)+x-2)\mid x+f(x-2)\implies2\mid x+f(x-2)$$$$\implies x\equiv f(x-2)(mod\text{ }2).$$$$P(x-1,x-2): f(f(x-1)+x-2)\mid x-1+f(x-2)\equiv1(mod\text{ }2)\implies f(x-1)=1.$$From this, we conclude that $f(x+1)=1$. If $f(x+2)=1$, then: $$P(x+2,x-1): f(f(x+2)+x-1)\mid x+2+f(x-1)$$$$\implies 2\mid x+3,$$and $$P(x+1,x-1): f(f(x+1)+x-1)\mid x+1+f(x-1)$$$$\implies 2\mid x+2,$$and we get a contradiction. By $P(x+1,x-1)$ we conclude, then, that $f(even)=2$ and $f(odd)=1$, for large $x$. $\textbf{Claim 1:}$ $f(x)\equiv x(mod\text{ }2)$, for $x>1$. $\textbf{Proof:}$ Let $N$ be such that $f(x)\in\{1,2\}$ for all $x>N$. Suppose $N$ is even (for $N$ odd is similar). For $x>N$ our claim is already proved. From: $$P(N,N+1): f(f(N)+N+1)\mid N+1\implies f(N)\text{is even}.$$Suppose by induction that for $n_0\leq n$ we have $f(N-n_0)\equiv N-n_0(mod\text{ }2)$. Then: $$P(N-n+1,N-n-1): f(f(N-n+1)+N-n-1)\mid N-n+1+f(N-n-1).$$See that $$f(N-n+1)\equiv N-n+1(mod\text{ }2)\implies f(N-n+1)+N-n-1\equiv0(mod\text{ }2)$$and thus $f(f(N-n+1)+N-n-1)$ is even. From this we conclude that $f(N-n-1)\equiv N-n-1(mod\text{ }2)$, as desired. $\square$ $\textbf{Claim 2:}$ $f(x)=1$ for all $x>1$ that is odd. $\textbf{Proof:}$ Take $p$ to be a big prime and $n$ an odd number. We have: $$P(p-f(n-1),n-1): f(f(p-f(n-1))+n-1)\mid p.$$See that $p-f(n-1)$ is odd, and since $p-f(n-1)$ is large we have $f(p-f(n-1))=1$, which implies that $f(n)\mid p$ and thus $f(n)=1.$ $\square$ $\textbf{Claim 3:}$ Take $p$ to be a big prime and $n$ an even number. We have: $$P(2p-f(n-1),n-1): f(f(2p-f(n-1))+n-1)\mid 2p\implies f(n)\mid2p\implies f(n)=2. \square$$We can check that any odd value can be assigned to $f(1)$. Therefore: $$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\text{ is odd;}\\2\text{ if }x\text{ is even.}\end{cases}$$where $k$ is an odd positive integer. Now, if for $x>>0$ we have $f(x)=1$, take any integer $N>1$ and a large prime $p$. See that from: $$P(p-f(N-1),N-1): f(f(p-f(N-1))+N-1)\mid p\implies f(N)\mid p\implies f(N)=1.$$We can assign any value for $f(1)$ and from this last case we get: $$f(x)=\begin{cases}k\text{ if }x=1;\\1\text{ if }x\ne1.\end{cases}$$From this we conclude the problem. $\blacksquare$

Solution from Twitch Solves ISL: There are three families of solutions: $f$ is the identity function; $f(n) = 1$ for $n \ge 2$, where $f(1)$ is any positive integer. $f(n) = 2$ for $n$ even, $f(n) = 1$ for odd $n \ge 3$, and $f(1)$ is any odd positive integer. The verification is easy, so we prove these are the only solution. The proof is split into two main cases. Case where $f$ is not injective Let \[ T = \min_{f(a)=f(b), a<b} (b-a). \]Then all outputs of $f$ are eventually divisors of $T$, as \[ f(y+f(a)) = f(y+f(b)) \mid \gcd(f(y)+a,f(y)+b) \mid b-a \qquad \forall y > 0. \]Claim: We have $T \le 2$. Proof. If $T > 2$, then look any $T$ consecutive outputs. They were supposed to be distinct divisors of $T$, impossible for $T > 2$. $\blacksquare$ If $T=1$, then for any $n \ge 2$, let $y=n-1$ and let $x$ be a large integer. Then we have $f(n) \mid x + f(n-1)$ for all large $x$, forcing $f(n)+1$. If $T=2$, then it follows $f$ must alternate between $1$ and $2$ eventually. Again, $f(n) \le 2$ follows for $n \ge 2$ as in the previous case, by letting $y=n-1$ and $x$ be large with $f(x)=1$. We can then quickly verify that only the situation where $f(\text{even})=\text{even}$ bears solutions, the ones we claimed earlier. Case where $f$ is not injective Let $c = f(1)$. Taking $x=1$ then gives \[ f(y+c) \le f(y)+1. \]This implies \[ f(n) \leq \frac 1c n + \max \left\{ f(1), \dots, f(c) \right\}. \]For $f$ to be injective, we must then have $c=1$. Finally, $f(y+1) \le f(y)+1$ together with $f$ injective then forces $f$ to be the identity function, by induction.

Nice! The solutions are \[f(x)=x\text{, }f(x)=1\text{ for }x>1\text{ and }f(x)=x\pmod2\text{ for }x>1.\]For $y\rightarrow y-f(x)$ we get \[f(y)\mid x+f(y-f(x)\text{ when }y>f(x)\text{ and denote this with }Q(x,y).\]We do cases whether $f$ is bounded or not. First, assume it's not. If $f(a)=f(b)$, $Q(a,y)$ and $Q(b,y)$ give $f(y)\mid a-b$ and choosing $f(y)$ large we get injectivity. Claim: The sequence of new maximums of $f$ eventually has common difference $1$. Proof. Let $f(a)$ be some term of the sequence with $a>f(1)$. $Q(1,a)$ gives $f(a)\mid 1+f(a-f(1))$ and because $f(a)>f(a-f(1))$ we have equality. This, with injectivity, gives that $f(n+1)=f(n)+1$ for all sufficiently large $n$. Thus, $f(n)+1=f(n+1)=f(n-f(1))\Rightarrow f(1)=1$. Hence $f$ is the identity (again, due to the Claim and injectivity). Now suppose $f<M$ is bounded. Note that for any prime $p>M$, setting $x=p-f(y)$ gives $f(f(p-f(y))+y)=1$ since it can't be $p$. Let $f(a)$ be a maximum of $f$ on $(1,+\infty)$, then $Q(p-f(a),a)$: \[f(a)\mid f(p-f(a))+a+f(a-1)\Rightarrow f(p-f(a))\stackrel{\text{over }p}{=}\text{constant}\]since $f(p-f(a))\le f(a)$. For two choices $p$ and $q$, like in the injectivity proof above, we get $f(a)\mid p-q$ and by Dirichlet's theorem this forces $f(a)\mid 2$. From here, check cases on $f(2)$. If $f(2)=1$ and $f(a)=2$ for some $a>1$, $Q(f(a),a)\Rightarrow f(a)\mid f(a-1)$ and by induction $f(2)=2$. Hence we get the second solution. If $f(2)=2$ by the above we have $f(a)\mid f(a-2)$ ($a>2$) and if $f(a)=f(b)=2$ when $a>3$, $Q(b.a)\Rightarrow 2\mid b$. To finish it's enough to show there are large preimages of $2$. Claim: If $f(x)=1$ for all $x>C$ we have $f(x)=1$ for $x>1$. Proof. Take $x$ large in $Q$.

The answer is $f(x)=x$, $f(x)=1$ for $x \geq 2$ with $f(1)$ arbitrary, or $f$ sending evens to $2$ and odds to $1$, except for $f(1)$ which can be an arbitrary odd. These clearly work. Let $P(x,y)$ denote the assertion. First suppose that $f$ is unbounded. Then if $f(a)=f(b)$ by comparing $P(a,y)$ with $P(b,y)$ we find that $f(z) \mid a-b$ for all $z>f(a)$, hence $a=b$. On the other hand, for any fixed $t$ we have $f(f(t)+y) \leq t+f(y)$, hence $f(x)$ is bounded above by $\tfrac{t}{f(t)}x+C$ for some suitable choice of $C$ depending on $t$ (by induction, starting with $f(1)$ through $f(f(t))$). Hence $f(t) \leq t$, otherwise by pigeonhole $f$ cannot be injective. But this holds for all $t$, hence $f(t)=t$ by injectivity again. Now suppose $f$ is bounded. Take $b>a$ with $b-a$ minimal such that $f(b)=f(a)$; by comparing $P(a,y)$ with $P(b,y)$ it follows that all sufficiently large $z$ satisfy $f(z) \mid b-a$. But now take some large $M$ and consider $f(M),f(M+1),\ldots,f(M+(b-a-1))$, which should be pairwise distinct but all divisors of $b-a$, hence $b-a \leq 2$. If $b-a=1$ then $f(x)=1$ for $x \geq 2$, and it is clear that $f(1)$ can be anything. If $b-a=2$ then we find that $f(\text{even})=2$ and $f(\text{odd})=1$ for all inputs at least $2$, since the other case yields a contradiction by making $x$ and $y$ both odd. Then $f(1)$ is odd from $P(1,1)$. This finishes the problem. $\blacksquare$

Solved (and typed up) with MathLuis. The answer is \[\boxed{f(n)=n}, \boxed{f(n)=\begin{cases}\text{anything}&n=1\\1&n\ge2\end{cases}}, \boxed{f(n)=\begin{cases}\text{anything odd}&n=1\\2&n\text{ is even}\\1&\text{otherwise}\end{cases}}.\]The first function clearly works, the second function works as the LHS is always $1$, and the third function works because the only way the LHS is $2$ is if $x+y$ is even, which will have the RHS be even as well. If $f$ is injective then let $c=f(1)$, we have that $f(x) \ne f(x+c)$, so assume there exists $x$ with $f(x)+1 \ne f(x+c)$ then $f(x)>f(x+c)$ because we have $f(x+c) \mid f(x)+1$ from $P(1,x)$. Now by an easy induction we can prove $f(x)>f(x+nc)$ for all positive integers $n$ therefore at some point some $f(x+kc)=0$ which can't happen, therefore for all positive integers $x$ we have $f(x+c)=f(x)+1$ therefore $f(x+nc)=f(x)+n$, now by $P(x,y+nc)$ we have $f(f(x)+y)+n \mid x+f(y)+n$ but fix $x,y$ and let $n$ be large enough, this is enough to conclude that $f(f(x)+y))=x+f(y)$ for all integers $x,y$. Call this $Q(x,y)$ then by $Q(x+c^2,y)$ we have $f(f(x)+y)+1=f(f(x)+y+c)=x+c^2+f(y)$ which implies $c^2=1$ and therefore $c=1$ so $f(1)=1$ and now as $f(x+1)=f(x)+1$ by an easy induction we have that $f(n)=n$ for all positive integers $n$ as desired. Now suppose that $f$ is bounded. Then let the maximum value of $f$ that occurs infinitely many times be $T$. Let the minimum nonzero $|a-b|$ such that $f(a)=f(b)$ be $D$(this has to exist as $f$ is bounded). Assuming $f(a)=f(b)$, subtracting $P(a,y)$ and $P(b,y)$(obviously they have the same LHS) gives \[f(f(a)+y)\mid |a-b|.\]Therefore, the values of $f$ that occur infinitely many times have to divide $D$, meaning that $T\le D$. Therefore, for large enough $x$, $f(x)\le T\le D$. However, note that since $D$ is minimal, $f$ must cycle through everything that is $\le D$ in the same order forever. Thus $T=D$, so, $f$ is eventually periodic with period $T$. However, note that the values of $f$ have to divide $D$, meaning that $d(D)=D$, which is only true when $T=D\le 2$. Case 1. $T=1$. Then there exists some $M$ such that for all $x\ge M$, we have $f(x)=1$. Then $P(M,y)$ and $P(M+1,y)$ give \[f(1+y)\mid M+f(y)\]and \[f(1+y)\mid M+1+f(y),\]respectively, so $f(1+y)=1$ for all $y$, meaning that $f(x)=1$ for all $x\ge 2$. Case 2. $T=2$. Then note that $f$ can alternate in two ways for large $x$($12121212\dots$ or $21212121\dots$). Setting $x$ and $y$ to be sufficiently large and the same parity, the LHS will be $2$, so $x$ and $f(x)$ must be the same parity for all large $x$. Thus there exists some $M$ such that for all $x\ge M$, $x\equiv f(x)\pmod 2$ and $f(x)\le 2$. Similarly to the first case, subtracting $P(M,y)$ and $P(M+2,y)$ gives $f(1+y)\mid 2$ for all $y$, so $f(x)\le 2$ for all $x\ge 2$. Now note that $D=T=2$, meaning that we cannot have consecutive values be the same, so indeed $x\equiv f(x)\pmod 2$ for all $x\ge 2$ as well, meaning that $M\le 2$. Finally, $P(1,2)$ gives \[f(f(1)+2)\mid 3,\]so $f(1)$ has to be odd. We are done! $\blacksquare$

v_Enhance wrote: Solution from Twitch Solves ISL: There are three families of solutions: $f$ is the identity function; $f(n) = 1$ for $n \ge 2$, where $f(1)$ is any positive integer. $f(n) = 2$ for $n$ even, $f(n) = 1$ for odd $n \ge 3$, and $f(1)$ is any odd positive integer. The verification is easy, so we prove these are the only solution. The proof is split into two main cases. Case where $f$ is not injective Let \[ T = \min_{f(a)=f(b), a<b} (b-a). \]Then all outputs of $f$ are eventually divisors of $T$, as \[ f(y+f(a)) = f(y+f(b)) \mid \gcd(f(y)+a,f(y)+b) \mid b-a \qquad \forall y > 0. \]Claim: We have $T \le 2$. Proof. If $T > 2$, then look any $T$ consecutive outputs. They were supposed to be distinct divisors of $T$, impossible for $T > 2$. $\blacksquare$ If $T=1$, then for any $n \ge 2$, let $y=n-1$ and let $x$ be a large integer. Then we have $f(n) \mid x + f(n-1)$ for all large $x$, forcing $f(n)+1$. If $T=2$, then it follows $f$ must alternate between $1$ and $2$ eventually. Again, $f(n) \le 2$ follows for $n \ge 2$ as in the previous case, by letting $y=n-1$ and $x$ be large with $f(x)=1$. We can then quickly verify that only the situation where $f(\text{even})=\text{even}$ bears solutions, the ones we claimed earlier. Case where $f$ is not injective Let $c = f(1)$. Taking $x=1$ then gives \[ f(y+c) \le f(y)+1. \]This implies \[ f(n) \leq \frac 1c n + \max \left\{ f(1), \dots, f(c) \right\}. \]For $f$ to be injective, we must then have $c=1$. Finally, $f(y+1) \le f(y)+1$ together with $f$ injective then forces $f$ to be the identity function, by induction. The second case you mean $f$ is injective.