Proposed by Ariel García, Mexico

Great problem We’ll split into two cases. Case 1: $f$ is unbounded. In that case, let $n_1<n_2<...$ be an infinite sequence of integers such that $f(n_i) > f(n_i-1), f(n_i-2), \dots, f(1)$ for each $i$. For any positive integer $k$ take large $i$ so that $f(n_i-k) \mid f(n_i-k-1) + f(1)$. Note that $f(n_i)\mid f(n_i-k) + f(k) < 2f(n_i)\implies f(n_i-k)=f(n_i)-f(k)$ and similarly $f(n_i-k-1) = f(n_i) - f(k+1)$. Therefore we have that $f(n_i) - f(k) \mid f(n_i)-f(k+1) + f(1)$, hence $f(n_i)-f(k) \mid f(1)+f(k)-f(k+1)$. As $i$ increases $f(n_i)-f(k)$ gets arbitrarily large, implying $f(k+1)=f(k)+f(1)$ for all $k$, so $f(n)=nf(1)$ and $f(1)>1$ divides each $f(n)$, and we’re done. Case 2: $f$ is bounded by some $M$. For any $p$ and $n>m$, note that $p\mid f(n),f(m)$ implies $p\mid f(n-m)$ because $f(n)\mid f(m)+f(n-m)$. Consider primes $p$ that divide infinitely many $f(n)$ and let $S$ be the set of all such primes. Let $u$ be the smallest positive integer with $p\mid f(u)$; it follows that for any $n$ with $p\mid f(n)$, we have $p\mid f(n-u), f(n-2u), \dots, f(n \pmod u)$, which contradicts the minimality of $u$ unless $u\mid n$. Notice this allows us to associate each prime $p$ with an “order” $u_p=u$ such that $p\mid f(n)\implies u_p\mid n$. Suppose for contradiction that $u_p\neq 1$ for each $p\in S$. Now clearly $S$ is finite, and if $m_k= k\text{lcm}_{p\in S} u_p + 1$, then $u_p\nmid m_k$ for each $p\in S$ and each $k$, so no $p\in S$ can divide $f(m_k)$. But the sequence $f(m_1), f(m_2), \dots$ is bounded and infinite, so it takes some value greater than one infinitely many times, meaning there is a prime $q$ which divides infinitely many of the $f(m_i)$. But this would imply $q\in S$, contradiction. Therefore it follows that some $p\in S$ has $u_p=1$. But now by definition there are arbitrarily large $n$ with $p\mid f(n)$, and $p\mid f(n), f(1)\implies p\mid f(n-1)$, so this implies $p\mid f(n)$ for all $n$, and we’re done.

This was Indian TST D2 P3. Here's my solution to this at TST: Case-1 $\text{Im}(f)$ is bounded. Proof: Call a prime $p$ to be Soumil if there's infinitely many integers $i$ such that $p|f(i)$. For a soumil prime $p$, define it's lavil to be the set $T_p : \overset{\text{def}}{=} \{ i \in \mathbb{N} : p | f(i) \}$. Note that if $a, b \in T_p$ then $|a-b| \in T_p$, thus (say by Euclidean algorithm), there's an integer $g_p \in \mathbb{N}$ such that $T_p = g_p \mathbb{N}$. Let $S$ be the set of all soumil primes. Now I claim atleast one of $g_p$ where $p \in S$ will be equal to $1$ (which would imply the proof). Assume not. Then define $S : \overset{\text{def}}{=} \prod_{p \in S} g_p$, and consider the set $Q = \{ Sm+1 \}_{m \in \mathbb{N}}$ where $m$ varies over integer. Note that by definition of soumil primes, the union of all lavil sets contains all but finitely many integers. But the elements of $Q$ don't belong to any lavil set, which is a contradiction so done. $\square$ Case-2 $\text{Im}(f)$ is unbounded. In this case I prove $f(m) = f(1)m$. Lemma: (Growth of $f$) We say the interval $[i, j]$ is soumil $f(n+1)-f(n) = f(1)$ for each $n \in [i, j]$. For each positive integer $m$, there're infinitely many soumil intervals of the form $[mk, m(k+1)-1]$.

So pick any integer $j$, and an integer $M > \max(f(1), f(2), \cdots, f(j))+100$, and a soumil interval $[n, 2^M+n]$. Then $f(n+M+j) = f(n)+(M+j)f(1) > M + jf(1) > \max(jf(1), f(j))$, and thus \begin{align*} f(n+M+j) & | f(n+M) + f(j) = f(n) + Mf(1)+f(j) \\ & | f(n+M+j-1) + f(1) = f(n) + (M+j)f(1) = f(n) + Mf(1) + jf(1) \end{align*}so subtracting them gives $f(n+M+j) | f(j) - jf(1)$ which gives the conclusion $\square$.

This was proposed by me I hope you all enjoyed it/will enjoy it!

The following solution splices together ideas from both of the official solutions. Claim: Let $d_n = \gcd(f(n), f(1))$. Then $d_{n+1} \mid d_n$ for all $n$. Proof. Immediate from $f(n+1) \mid f(n) + f(1)$. $\blacksquare$ Hence, we will assume henceforth that $d_n = \gcd(f(n), f(1)) = 1$ for all $n \ge C$, for some constant $C$ (otherwise $\min_n d_n$ is the required constant). Claim: If $\gcd(a,b) = 1$, then $\gcd(f(a), f(b)) \mid f(1)$. In particular, $\gcd(f(a), f(b)) = 1$ if $\min(a,b) \ge C$. Proof. This follows by Euclidean algorithm: if $a > b$ then $f(a) \mid f(a-b) + f(b)$, so $\gcd( f(a), f(b) ) \mid \gcd( f(a-b), f(b) )$. $\blacksquare$ The second claim already implies $f$ is unbounded: if $f$ takes only values in $\{2, \dots, L\}$ then taking any $L+1$ primes larger than $C$ gives a contradiction. Main induction: Assume $f$ is unbounded. Let $X$ be a local maximum, meaning $Y = f(X) \ge \max \left\{ f(1), \dots, f(X-1) \right\}$. We will assume $X$ and $Y$ are large enough such that $X > C + C f(1)$, $Y > 2 f(1) f(C)$. Then: \begin{align*} Y = f(X) \mid f(X-C) + f(C) &\implies f(X-C) = Y - f(C) \\ Y-f(C) = f(X-C) \mid f(X-2C) + f(C) &\implies f(X-2C) = Y - 2f(C) \\ Y-2f(C) = f(X-2C) \mid f(X-3C) + f(C) &\implies f(X-3C) = Y - 3f(C) \\ &\vdotswithin{\implies} \\ &\implies f(X-f(1)C) = Y - f(1) f(C). \end{align*}However, all the right-hand sides are supposed to not be divisible by $f(1)$, yet we assumed $\gcd(f(C), f(1)) = 1$, contradiction.

Here is a short solution by Gems98. First, we make the following observation. Claim: If $d\mid f(m)$ and $d\mid f(n)$ then $d\mid f(m-n)$. Proof: Obvious from the problem's condition. We will consider two cases. Case 1: $f$ is bounded. Let $p_{1}$ be a prime number. By Dirichlet's theorem, there exists a sequence of prime numbers $p_{2}, p_{3}, \cdots, $ such that $$p_{n+1} \equiv 1 \pmod{\prod_{i=1}^{n}p_{i}}$$By pigeonhole principle, there exists a increasing sequence $a_{1}, a_{2} ,\cdots$ such that $$c = f(p_{a_{1}}) = f(p_{a_{2}}) = \cdots$$From $p_{a_{i+1}} \equiv 1 \pmod{p_{a_{i}}}$, we get $c \mid f(1)$ by applying the Claim repeatedly. Therefore, if $c \mid f(n)$ then $c \mid f(n-1)$. Since the sequence $p_{a_{i}}$ is unbounded, we get $c \mid f(n)$ for every $n \in \mathbb{Z}^+$ which is the desired result. Case 2: $f$ is unbounded. We call the natural number $n$ $\textit{good}$ iff $f(n) > \max\{f(1), \cdots, f(n-1)\}$. Since $f$ is unbounded, there exist infinitely many $\textit{good}$ number. It's easy to show that if $m$ is $\textit{good}$, then $f(m) = f(i) + f(m-i)$ for all $i \leq m-1$. Let $n$ be a positive integer and $m$ be a sufficiently large $\textit{good}$ number. From the condition, we get \begin{align*} f(m-n+1) &\mid f(m-n)+f(1) \\ f(m) - f(n-1) &\mid f(m) - f(n) + f(1) \\ f(m) - f(n) &\mid f(n) - f(n-1) - f(1) \end{align*}Since $m$ is sufficiently large, we get $f(n) - f(n-1) - f(1) = 0$ which implies that $f$ is linear. Therefore, there exists positive integer $c = f(1) > 1$ such that $c\mid f(n)$ for all $n \in \mathbb{Z}^+$.

While this problem is a really nice one, I would like to point out some similar (and difficult) problems that have appeared before, namely 2007 N5, IMO 2011, Iran 3rd round 2017, and with a different condition Romania TST 2016.

Yeah, there are some other pretty cool NT functional problems around. I definitely got reminded of some of those when I came up with this problem I learned of the existence of the Romania TST problem because I heard this one was discarded from the shortlist due to it, which was a shame . Had I known that problem existed beforehand I may have not sent my problem to be considered for IMO.

We split into cases based on whether $f$ is bounded or not. First, assume $f$ is unbounded. This means that there is an infinite sequence of \textit{peaks} $1=x_0<x_1<x_2<\cdots$ such that $f(x_n)>f(x)$ for all $x<x_n$. Note that $f(x_n)\mid f(x)+f(x_n-x)$ and $f(x)+f(x_n-x)<2f(x_n)$, so in fact $f(x_n)=f(x)+f(x_n-x)$. For any given $x$, we have for large enough $n$ that $f(x_n-x)\mid f(1)+f(x_n-x-1)$, so \[f(x_n)-f(x)\mid f(1)+f(x_n)-f(x+1),\]so $f(x_n)-f(x)\mid f(1)+f(x)-f(x+1)$ for arbitrarily large $n$. We see that $f(x_n)$ can be arbitrarily large, so we must have $f(x+1)=f(x)+f(1)$, so $f(x)=xf(1)$. Thus, $f(1)\mid f(n)$ for all $n$. Now suppose $f$ is bounded. Note that $f(n+1)\mid f(n)+f(1)$, so $\gcd(f(n+1),f(1))\mid\gcd(f(n),f(1))$. Thus, \[\cdots\mid\gcd(f(3),f(1))\mid\gcd(f(2),f(1))\mid\gcd(f(1),f(1)),\]so either $\gcd(f(n),f(1))=1$ for large enough $n$, or $\gcd(f(n),f(1))>1$ for all $n$, in which case we're done. So WLOG, suppose that $\gcd(f(n),f(1))$ for all $n\ge N$. We claim that $\gcd(f(x),f(xy+1))=1$ for $x\ge N$. To see this, note that \[f(xy+1)\mid f(x)+f(x(y-1)+1)\implies\gcd(f(xy+1),f(x))\mid\gcd(f(x(y-1)+1),f(x)).\]Iterating this gives $\gcd(f(xy+1),f(x))\mid\gcd(f(1),f(x))=1$, as desired. Thus, any two terms in \[f(N),f(N+1),f(N(N+1)+1),f(N(N+1)(N(N+1)+1)+1),\ldots\]are relatively prime, so in particular, any two terms are distinct. But this is an infinite sequence of $f(x)$ for distinct values of $x$, so $f$ is unbounded, which is the desired contradiction.

This is the first shortlist #6 that I solve(This is also the few ones that I have attempted), and spend a lot of time (10+ hours), so I decided to post it on the thread. Let $a_n=f(2^n)$ for all $n\geq 0$. We distinguish two cases: $\underline{Case I:}$For all $n\geq 0$, $a_n$ has an odd prime factor note that by taking $m=n=2^k$ we have $$a_k|2a_{k-1}$$Hence any prime factors of $a_n$ must also be a prime factor of $a_i$ where $i$ is any positive integer less than $i$. Since $a_1$ has only finitely many prime factors, there exists a prime p such that $p|a_n$ for all positive integers $n$. We that $p|f(n)$ for all $n\in\mathbb N$. Indeed, we proceed by backward induction to show that every integer in the interval $[2^k,2^{k+1}]$ has this property, indeed we have $p|f(2^{k+1})$. Now note that if $p|f(n)$ then since $p|f(1)$ together with $$f(n)|f(n-1)+f(1)$$we have $p|f(n-1)$ and therefore we complete the inductive step and therefore we're done. $\underline{Case II:}$There exists $k\in\mathbb N$ such that for all $N\geq k$ we have the fact that $a_n$ is a power of $2$.(We assume that $k$ is the minimal choice) Using similar arguments as in case I we have that for every number $m$ there exists a number $k$ such that for all $N\geq k$ we have $f(m\cdot 2^k)$ is a power of 2. Note that if $p|f(m)$ and $p|f(n)$, then we have $p|f(n-m)$ therefore $p|f(gcd(m,n))$ by Euclidean algorithm. That is $$gcd(f(m),f(n))|f(gcd(m,n))(1)$$Let $q$ be the minimal number such that $a_q$ is even. We claim that if $v_2(n)<q$ then $f(n)$ is odd. Otherwise, suppose $v_2(n)=s$, by $(1)$ we have $$2|gcd(f(n),f(2^k))|f(gcd(f(n),f(2^k))=f(2^s)$$this contradicts the minimality of $q$ We further distinguish two cases $\underline{Case IIa:}$$q\geq1$ We prove the following $\underline{CLAIM 1.}$The sequence $\{a_n\}$ is unbounded $\underline{Proof.}$Suppose $\{a_n\}<M$ for all $n$, then since $$f(2^n+1)|f(2^n)+f(1)$$We have $f(2^n+1)\leq f(2^n)+f(1)\leq M+f(1)$ hence $f(2^n+1)$ is also bounded, therefore by pigeonhole principle there exists an infinite sequence of numbers $\{b_n\}$ such that $$f(2^{2^{b_i}}+1)=f(2^{2^{b_j}}+1)$$for all $i,j\in\mathbb N$.Let this number be $c$, then since $(2^{2^{b_i}}+1,2^{2^{b_j}}+1)=1$, from $(1)$ we have $c|f(1)$, using the same induction method as in Case I we have $c|f(n)$ for all positive integer $n$, contradiction. $\underline{CLAIM 2.}$ Let $a$ be an integer, denote $v_2(n)$ by $m$, then $$v_2(f(a))=v_2(f(2^m))$$$\underline{Proof.}$Suppose $a=2^mp$, and $v_2(f(a))=x$, $v_2(f(2^m))=y$ If $x>y$, then we prove by induction that $v_2(f(an+2^m))\leq y$ for all positive integers $n$ Indeed the base cases are trivial, suppose the case n holds, then $$v_2(f(a(n+1)+2^m))\leq v_2(f(an+2^m)+f(n))\leq y$$so we're done. In particular, let $d$ be the order of $2$ mod $p$, pick n such that $np+1=2^wd$ for all integer $w$, we obtain that $v_2(a_{wd+m})=y$, and since $v_2(a_i)+1\geq v_2(a_{i+1})$ we must have $v_2(a_n)\leq y$ that is, $a_n$ is bounded, which violates CLAIM 1. If $y>x$, then we prove by induction that $v_2(f(a+n2^m))\leq x$ for all positive integers $n$ Indeed the base cases are trivial, suppose the case n holds, then $$v_2(f(a+(n+1)2^m))\leq v_2(f(a+n2^m)+f(2^m))\leq x$$so we're done. pick n such that $n+p+1=2^w$ for all integer $w$, we obtain that $v_2(a_{w})=x$, that is, $a_n$ is bounded, which violates CLAIM 1. Combining the two cases, we proves the claim. $\underline{CLAIM 3.}$If $a\geq k$, then $$v_2(f(2^{a+1})=v_2(f(2^a))+1$$$\underline{Proof.}$ Otherwise, since $v_2(f(2^{a+1})\leq v_2(f(2^a))+1$ either (i)$v_2(f(2^{a+1})<v_2(f(2^a))$ or (ii)$v_2(f(2^{a+1})=v_2(f(2^a))$ If $(i)$ holds, $$v_2(f(2^a))>v_2(f(2^{a+1})=v_2(f(2^{a+1})+f(2^a))\geq v_2(f(2^{a+1}+2^a))$$This violates CLAIM 2 since $v_2(2^{a+1}+2^a)=v_2(2^a)$ If $(ii)$ holds, then we let $f(2^a)=2^m$. We prove by induction that $$f(n2^a)=2^m$$for all integer $n$ not divisible by $4$. Indeed from $(ii)$ we have $f(2\cdot 2^a)=2^m$ Now suppose all smaller cases holds, we have $$f(n2^a)| f((n-1)2^a)+f(2^a)=2^{m+1}$$From CLAIM 2 we have $v_2f(n2^k)=m$ and therefore $f(n2^k)=2^m$, this completes the inductive step. Now we have, for all integers $b$, $$f(2^{b+m})|f(2^m)+f((2^b-1)2^m)=2^{a+1}$$that is $a_n$ is bounded, this violates CLAIM 1, so we prove CLAIM 3. $\underline{CLAIM 4.}$ For all integer $n$ we have $$f(n2^k)=n2^m$$$\underline{Proof.}$ We proceed by induction. In the following we denote $f(2^k)=2^m$. Note that $CLAIM 3$ implies that for all integer $b$ we have $f(2^{b+k})=2^{m+b}$ The base cases are trivial. Now suppose all smaller cases hold we consider the case $n$,suppose $2^{t-1}\leq n\leq 2^t$, we have $$f(n2^k)|f((n-1)2^k)+f(2^k)$$$$f(2^t\cdot 2^m)|f(n2^k)+f(2^t-n)2^k)$$applying the inductive hypothesis we have $$n2^m\leq f(n2^k)\leq n2^m$$This completes the inductive step and we hence have proof CLAIM 4. $\underline{CLAIM 5.}$ $$f(2^{k-1})=2^{m-1}$$$\underline{Proof.}$ Now we have $$f(n2^k+2^{k-1})|f(n2^k)+f(2^{k-1})$$$$f((n+1)2^k)|f(n2^k+2^{k-1})+f(2^{k-1})$$for all integer $n$. Let the terms on the left and right side of the first divisibility be $A$ and $B$, and the terms on the left and right side of the second divisibility be $C$ and $D$. Note that $A\leq B$ and $C\leq D$. If $A=B$ and $C=D$, we add them up and apply $CLAIM 4$ to get $$f(2^{k-1})=2^{m-1}$$which is what we want to prove. Otherwise, either one of $2A\leq B$ or $2C\leq D$ must hold. If the former holds we have $$2^m+f(n2^k+2^{k-1})\leq f(2^{k-1})$$since $f(n2^k+2^{k-1})\geq \frac{1}{2}n2^{m+1}+2^m$ we have $f(2^{k-1})\geq (n+1)2^{m+1}$ which can't hold for large $n$. If the latter holds we have $$(n+1)2^m\leq 2f(2^{k-1})$$which also can't hold for large $n$. So CLAIM 5 is proved. However, we define $k$ to be the minimal integer such that $f(2^k)$ is a power of $2$, so we obtain a contradiction, which rejects the case $q\geq 1$ $\underline{Case IIb.}$$q=0$ Now we have $f(1)$ is even, using the same reasoning as in Case I, we have that for all $n$, $f(n)$ is even, so we're done. Hence we reject all case and the proof is thus completed.

Hopefully this isn't equivalent to any previous solutions Nowhere near as pretty as the first one tho Notice that if $p|f(1)$ and $p|f(n)$, then $p|f(m)$ for all $m\leq n$. So for the sake of contradiction, assume that $(f(1),f(n))=1$ for all $n>N$, where $N$ is some integer. Claim 1: $f(n)\leq n+C$ where $C$ is a constant Also notice that $f(2n)|2f(n)$, so by induction we have $f(2^k)|2^kf(1)$, so $f(2^k)|2^k$ for $2^k>N$. Because $f(n+m)|f(n)+f(m)$, we also have $f(n+m)\leq f(n)+f(m)$. We will also use these two inequalities: $f(2^k)\leq 2^k$ for $k\geq \log_2(N)$ and $f(2^k)\leq 2^kf(1)$ for the smaller ones. Writing any $n$ as a sum of powers of two and using the inequality as many times as needed, we get $f(n)\leq n+(1+2+4+...+2^{\log_2(N)})f(1)\leq n+C$ where $C$ is constant. Claim 2: Let $a_p$ be the smallest value $n$ for which $p|f(n)$. Then we have $p|f(n)\implies a_p|n$ Assume the contrary and let $k$ be the smallest value for which $p|f(k)$ and $a_p\nmid k$. Then $k>a_p$ and we have $f(k)|f(k-a_p)+f(a_p)\implies p|f(k-a_p)$, a contradiction. We now split into two cases: Case 1 $f(n)\leq \frac{1}{2}(f(n-1)+f(1))$ for infinitely many values of $n$ Take some big $n$ and $\varepsilon>0$ such that $n+2C\leq n(1+\varepsilon)$. Notice that by our assumption we can make $\varepsilon$ arbitrarily small Take a big integer $m$ and write it as follows: $f(m)=f(an+b)\leq af(n)+f(b)\leq a\frac{1}{2}(f(n-1)+f(1))+f(b)\leq a\frac{1}{2}(n-1+C+1+C)+b+C$ $\leq \frac{1}{2}an(1+\varepsilon)+b\frac{1}{2}(1+\varepsilon)+n+C\leq (an+b)\frac{1}{2}(1+\varepsilon)+C+n = m\frac{1}{2}(1+\varepsilon)+n+C<\frac{3}{4}m$ for $m$ large enough, say for $m\geq N_0$. Take $M=max(N,N_0)$ (These inequalities are far from pretty but they work and obviously $3/4$ is arbitrary) Now look at primes that are larger then $M$ .Say the number of primes that divide $f(1)f(2)\cdots f(k)$ for some $k$ is $g(k)$. By claim 2, you can notice that all primes larger than $M$ are $a_p$ for some $p$, which means $g(k)\geq \pi(k)-\pi(M)$. Say the largest prime dividing $f(1)f(2)\cdots f(M)$ is $P$. Notice that for $k>\frac{4}{3}P$, $\pi(\frac{3}{4}k)\geq g(k)\geq \pi{k}-\pi{M} \iff \pi(k)-\pi(\frac{3}{4}k)\leq \pi(M)$, the right-hand side is fixed, and from here there are many ways to prove that this is a contradiction. (I won't be writing any of them because I can't think of an elementary way ) Case 2 $f(n)=f(n-1)+f(1)$ for $n\geq L$, where $L$ is some integer This means $f(m)=f(L)+f(1)(m-L) = mf(1)+(f(L)-Lf(1))$ for $m\geq L$. Remember we had the property of $f(2)$ to be a power of $2$. It is trivial to see that this forces $f(L)-Lf(1)=0$ and $f(1)$ is a power of $2$, meaning $2$ divides all $f(m)$ with $m\geq L$, contradiction

Nice problem ! We distinguish cases based on the boundedness of $f$. Case 1 : $\operatorname {Im}f$ is bounded. For all primes $p$, define the set $S_p= \{n : p\mid f(n)\}$. Call a prime $p$ strong , if $S_p$ is infinite and weak otherwise. Its easy to see that $p\vert f(a) , f(b) \implies p\mid f(a-b)$, hence $S_p=x_p \cdot \mathbb Z^{+}$ , for some $x_p$. Suppose that for all strong primes $p$, $x_p\neq 1$. Then note that since $f(n)$ is divisible by only finitely many weak primes, hence this means that the set $ \mathbb Z^+ \setminus { \bigcup_{p \quad \text{strong}} S_p } $ is finite. Consider, $X= \prod_{p \quad \text{strong}} x_p$ and look at $X\mathbb Z^++1$. Obviously its infinite and has $f(\bullet)$ not divisible by any strong prime, contradiction. $\blacksquare$. Hence $x_p=1$ for some strong prime $p$, and the conclusion is immediate. Case 2 : $f$ is unbounded. The idea is to worry only about the size of $f$ and force "Cauchyness" on some intervals. We show $f(x)=xf(1)$ for all $x\in \mathbb Z^+$ Call a $x$ to be a peak if $f(x) > \operatorname {max} \{f(1),f(2) ,\dots f(x-1)\}$. Obviously there are infinitely many such peaks due to unboundedness. Its easy to see that due to size issues, $f(x)=f(x-k)+f(k)$ holds for all $x>k$. We show $f(n+1)-f(n)=f(1)$ for all $n$. Pick a arbitrary $x$ and $y$ such that $x+y$ is a peak and $f(x+y)$ is huge. Spamming the equality $f(x+y)=f(x)+f(y)=f(x-1)+f(y+1)$, we get : $$ f(y+1) \vert f(y)+f(1) $$$$\implies f(x+y)-f(x-1) \mid f(x+y)-f(x)+f(1)$$$$\implies f(x+y)-f(x-1) \mid f(x)-f(x-1)-f(1)$$ Taking $f(x+y)$ to be huge we're done. $\blacksquare$

For the bounded case, just take a prime $p$ for which all the values of $f(n)$ appeared before $p$. So there is some $n$ smaller than $p$ such that $f(p)=f(n)=c$ and by euclidean algorithm $c$ divides $f(1)$, and by more application of euclidean algorithm (induct down, begin with $p,1$) we get $c$ divides every guy in $f(p-1), f(p-2), f(p-3) ... $ and so. we are done since by assumption every value of $f$ is included in this sequence.

Let $P(m, n)$ denote the assertion. First of all, $P(1, n)$ yields\[f(n+1) \mid f(n) + f(1) \implies \gcd(f(n+1), f(1)) \mid \gcd(f(n), f(1))\]always. Now, we only need to consider when there exists $M$ for which $\gcd(f(n), f(1)) = 1$ for all $n \geq M$ since\[\gcd(f(n), f(1)) \mid f(n) \mid \gcd(f(n-1), f(1))\]so the sequence $\gcd(f(i), f(1))_{i = 1}^{\infty}$ is in fact nonincreasing, and if it never hits $1$, then the lower bound $L$ of the sequence divides all $\gcd(f(i), f(1))$, and thus divides all $f(i)$, at which point we would be done. Next, we will prove that in the case where $f(n), f(1)$ are relatively prime for all sufficiently large $n \geq M$, then $f$ is unbounded. First, note that $P(n, m-n)$ yields $f(n) \mid f(m-n) + f(m)$ hence $\gcd(f(n), f(m)) \mid \gcd(f(m-n), f(n))$ which is analogous to the Euclidean Algorithm, and performing this continuously yields $\gcd(f(n), f(m)) \mid f(\gcd(m, n))$. Thus, for pairs $(m, n)$ that are relatively prime, and $m, n \geq M$, it follows that $\gcd(f(m), f(n)) \mid f(1)$ but since\[\gcd(f(m), f(1)) = \gcd(f(n), f(1)) = 1\]we know $\gcd(f(m), f(n)) = 1$. It easily follows that $f$ is then unbounded; if it were upper bounded by $U$, then just pick some $N > U$ numbers $a_1, \ldots , a_N \geq M$ for which their $f$ values are all pairwise relatively prime; no two $f(a_i)$ could be the same, hence the range of $f$ needs to hit at least $N > U$ numbers, thus $U$ could not have been the upper bound, a contradiction. Lastly, we finish by considering the case where $f$ is unbounded. Consider numbers $k$ for which $f(k) > f(1), \ldots , f(k-1)$. There are clearly infinitely many of these $k$, else $f$ is upper bounded by the largest $f(k)$. Pick arbitrarily large $K$ for which $f(K)$ is large, and greater than all $f(i)$ for $i < K$. Then for any positive $x + y = K$, note $f(x) + f(y) < 2f(K)$ but still must be a whole multiple of $K$, hence $f(x) + f(y) = K$. Note that since $f(x + 1) \mid f(x) + f(1)$,\[f(K) - f(y-1) \mid f(K) - f(y) + f(1) \implies f(K) - f(y-1) \mid f(y-1) - f(y) + f(1)\]where clearly $|f(y-1) - f(y) + f(1)| < |f(K) - f(y-1)|$ from picking $K$ such that $f(K)$ is much larger than every one of $f(y), f(y-1), f(1)$. Finally, this implies that $f(y) = f(y-1) + f(1)$ for all integers $y$, hence $f$ is linear and then induction easily shows that $f(y) = yf(1)$, so indeed $f(1) \mid f(y)$ for all $y$, finishing this case as well. After exhausting all cases, we have shown $f(1)$ does indeed always divide all $f(n)$.

Cool problem! . I did the bounded case first and then died on the unbounded case for a longg time proving useless stuff like $f(n) > n$ before I realised simple stuff does work Note that every value of $f$ has some prime dividing it since $f(n) > 1$. Let $p$ be an arbitrary prime dividing some value of $f$. Let $S_p$ denote the set of numbers $n$ such that $p | f(n)$. Note that $a,b \in S_p \implies |a-b| \in S_p$ as well, by the problem statement. Let $a_1 < a_2 < a_3, \cdots$ be the elements of $S_p$. Now, we must have $a_{k+1} - a_k = a_1$. This is because if $a_{k+1} - a_k = z < a_1$, then $z < a_1 \in S_p$, not possible. If $a_{k+1} - a_k = z > a_1$, then $a_{k+1} - a_1 \in S_p$ and is between $a_{k}$ and $a_{k+1}$, not possible. So, we have that $S_p$ is just multiples of $a_1$. Let $q$ be a prime dividing $f(1)$. If the problem is false, then $S_q$ is finite, say with maximal element $M$. Pick a prime $r > M$. Note that $f(r)$ cannot contain any prime divisor that divides $f(n)$ for $n < r$ since then we would need $n | r$, not possible since $n \neq 1$ and $r$ is prime. Since this is true for infinitely many $r$, we have that there are infinitely many primes dividing some value of $f$. In particular, $f$ is unbounded. I will in fact show that if $f$ is unbounded, then it is linear. Call a number $n$ a peak if $f(n) > f(k)$ for all $1 \le k \le n-1$. So $f(n) | f(k) + f(n-k)$ but since $f(n)$ is greater than both of them, we must have $f(n) = f(k) + f(n-k)$ for all $k < n$. Since $f$ is unbounded, there are infinitely many peaks. Let $m$ be one such peak. Observe that $f(m) - f(k) = f(m-k) | f(m-k-1) + f(1) = f(m) - f(k+1) + f(1) \implies f(m) - f(k) | f(k) + f(1) - f(k+1)$. Since we can make $m$ sufficiently large, we must have that the RHS is $0$, so $f(k+1) = f(k) + f(1)$ which gives $f(n) = nf(1)$ and so $c = f(1)$ itself divides all values of $f$. Therefore, we are done. $\blacksquare$

IndoMathXdZ wrote: Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$. Solved with MathLuis Let \(P(m,n)\) denote the assertion of the given functional equation. We split the problem into two cases. Case 1. \(\text{Im}(f)\) is bounded. From the divisibility condition \[f(n+1)\mid f(n)+f(1)\]we have that \[\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=\gcd(f(n),f(1))\]Also, by Pigeon Hole, there exists a prime \(p\) such that \(p\mid f(n)\) for infinitely many \(n\), let the set of such \(n\) be denoted as \(\mathbb{S}_p\) and let \(k\) be their greatest common divisor. By the Euclidean algorithm, we can show that \(\mathbb{S}_p\) contains all the multiples of \(k\). Now, we choose a subset \(\mathcal{S}\) of \(\mathbb{S}_q\) (for some prime \(q\)) so that \(\mathcal{S}\) contains the least element of \(\mathbb{S}_q\) and all the images of the elements are equal. Let the least element be \(n_0\), then note that \(\gcd(f(n_0),f(1))=\gcd(f(m),f(1))\) for all \(m\geq n_0\), because of the divisibility condition we got earlier. Now, if we choose the prime \(q\) so that it divides \(f(1)\), then we get that \(q\) divides \(f(i)\) and \(f(i+1)\) for some \(i\). And since the only \(k\) that divides \(i\) and \(i+1\) is \(1\), \(q\) divides \(f(i)\) for all natural numbers \(i\) as desired. Case 2. \(\text{Im}(f)\) is unbounded. Call a positive integer \(n\) gawaskar, if \(f(n)>f(i)\) for all \(i<n\). Note that there are infinitely many gawaskar numbers and \(f(n)=f(i)+f(n-i)\) for all \(i<n\). Now, let \(x+y\) be a gawaskar number such that \(f(x+y+1)\) is huge. Then, by the problem's condition, \[f(x+y+1)\mid f(x+y)+f(1)=f(x)+f(y)+f(1)\]and \[f(x+y+1)\mid f(x)+f(y+1)\]implying that \[f(x+y+1)\mid f(y+1)-f(y)-f(1)\]Implying that \(f(y+1)=f(y)+1\). Since there are infinitely many gawaskar numbers, we have that \(f(x+1)-f(x)=f(1)\) for all \(x\in\mathbb{N}\). This implies that \(f(x)=xf(1)\), and since \(1\neq f(1)\mid f(x)=xf(1)\), we are done.

Solved with help from Max Lu If $p$ divides $f(1)$, then first there's $n_p$ values of f divisible by p, then everything afterwards isn't divisible by p. Thus, there exists some $N$ s.t. for all $n\geq N$ you have $\gcd(f(1),f(n))=1$. If $p\nmid f(1)$, then let the first time that $q$ appears in $f(i)$ be $s_q$. Then, $p\mid f(n) \Longrightarrow s_q\mid n$. Combining these two results, for $p\geq N$, $f(p)$ is relatively prime to all previous numbers. Thus, if $f$ is bounded, you find a contradiction because you can't keep generating relatively prime numbers (finite number of prime divisors). Otherwise, if $f$ is bounded then we claim that $f$ is linear (and therefore of the form $f(n) = n\cdot f(1)$. There must be arbitrarily long chains of $f(n+1) = f(n)+f(1)$, otherwise if all chains were of length $\leq C$, then the value would go up by $Cf(1)$ and then get halved, which cannot become unbounded. Thus, there exists a chain with arbitrarily large $k$ of the form $[b-k,b]$. Next, $f(b)\mid f(b-k) + f(k) = f(b) - kf(1) + f(k) \leq f(b)$ so $f(k) = kf(1)$ and we're done. $\blacksquare$.

Assume otherwise. Notice that $f(m+n) \leq f(m)+f(n)$ so we can induct to $f(a_1+a_2+\ldots+a_n) \leq f(a_1)+f(a_2)+\ldots+f(a_n)$. We say a prime $p$ is alive if for any positive integer $N$, there exists $x \geq N$ such that $p \mid f(x)$. We say a prime is dead otherwise. Notice that for every $p \mid f(1)$ we have $p \nmid f(k)$ for some $k$, so $p$ is dead by induction because $p \nmid f(i) \Longrightarrow p \nmid f(i+1)$ since $f(i+1) \mid f(1)+f(i)$. We say a dead prime $p$ dies on a day $N$ if for any $x \geq N$ we have $p \nmid f(x)$ and such $N$ is minimal. By definition, every prime has a death day. Note that $f(2n) \mid 2f(n)$ so for an odd prime $p$ if $p \nmid f(n)$ then $p \nmid f(2n)$. Therefore no new primes appear in the sequence $f(1), f(2), f(4), \ldots, f(2^i), \ldots$ and eventually after all primes that divide $f(1)$ die, $f(2^n)$ is a power of $2$ for all $n \geq C$ for some $C$, and none of them are equal to $1$. This implies $2$ is alive, so $2 \nmid f(1)$. Therefore since $v_2(f(2^{i+1}) \leq 1+v_2(f(2^{i}))$ we know $v_2(f(2^i)) \leq i$. A corollary is that $f(2^i) \leq 2^i$ for all $i \geq C$. Assume at some integer $T$ we have $v_2(f(2^T)) < T$ then by induction $v_2(f(2^i))<i$ for all integers $i \geq T$. So for all $i \geq \max(T, C)$ we have $f(2^i) \leq \frac{2^i}{2}$ Let $S = \sum_{i = 0}^{\max(T, C)} \left(f(2^i)-2^i\right)$, which is a finite positive integer. Then for all $i \geq \max(T, C)$ we have $f(i) \leq \sum_{2^s \text{ in binary representation of i}} f(2^s) \leq \frac{i}{2}+S$ Let $R$ be the day when all primes that divide $f(1)$ die. Lemma: If $p \mid f(q)$ where $p, q$ are primes and $q \geq N$ for some constant $N$ then $p \nmid f(i)$ for all $i < q$. Proof: Choose $N = R$. Then assume $p \mid f(i)$ for some $i < q$, so pick the minimal such $i$ which must be greater than $1$. Clearly $i \nmid q$ so let $s$ be $q$ reduced modulo $i$. Then $p \nmid f(s)$, and by induction on $p \nmid f(k) \Longrightarrow p \nmid f(k+i)$ using $f(k+i) \mid f(i)+f(k)$, we prove $p \nmid f(q)$ which is a contradiction, so we are done. Therefore the set of primes between $R$ and $x$ for arbitrary $x$ has an injective mapping to the set of primes at most $\frac{x}{2}+S$. So $\pi\left(x\right) \leq \pi\left(\frac{x}{2}\right)+(R+S)$ for constant $R+S$. This is clearly false by the Prime Number Theorem, giving contradiction. Therefore $T$ doesn't exist, so $v_2(f(2^i)) = i$ for all $i$, implying $f(2^i) = 2^i$ for all $i \geq C$. Now let $M = \sum_{i = 0}^C \left(f(2^i)-2^i\right)$. Clearly by summing over the binary representation again, $f(i) \leq i+m$ for all $i$. By taking the smallest power of 2 greater than $i$, $2^k$, we know that $2^k \leq f(i)+f(2^k-i)$ so $f(i) \geq i-M$ since $f(2^k-i) \leq 2^k-i+M$. For $i, j > 2M$ we must have $f(i+j) \mid f(i)+f(j)$ but if $f(i+j) \neq f(i)+f(j)$ then $i+j-M \leq f(i+j) \leq \frac{f(i)+f(j)}{2} \leq \frac{i+j}{2}+M$, which is a contradiction. So $f(i+j) = f(i)+f(j)$. So letting $j = ki$ and inducting on positive integers $k$ gives us that $f(ki) = kf(i)$ for $i > 2M$. However this means if $p$ is any prime that divides $f(1)$, then $p \mid f(pi) = pf(i)$ for arbitrarily large $i$. This means $p$ is alive, so by contradiction we are done.

I didn't like this as much as most others.

Really long solution, but this problem feels like you just keep throwing stuff at it and keep track of what you've proved and you eventually grind it down. As with everyone else, split into cases where $f$ is bounded and unbounded. In general, note that if $n \mid f(a),f(b)$ for $a>b$, then $n \mid f(a) \mid f(b)+f(a-b) \implies n \mid f(a-b)$. Call an integer $i$ with $n \mid f(i)$ $n$-cool. I claim that if there exist $n$-cool integers, then they are all consecutive multiples of some positive integer $k$, and $k$ is one of them (i.e. they are $\{k, 2k, \ldots\}$ or $\{k, 2k, \ldots, ak\}$ for some $a \geq 1$). I claim that setting $k$ equal to the least $n$-cool integer works, which is by induction. Suppose that the $c$ smallest $n$-cool integers are $\{k,\ldots,ck\}$, and the $c+1$-th smallest $n$-cool integer exists. Then if $x$ is this $c+1$-th smallest $n$-cool integer, $x-k$ must be $n$-cool as well, and also must be in $S$ as it's smaller than $x$, hence $x-k=ck \implies x=(c+1)k$, completing the induction. Suppose $f$ is bounded, so there exists some maximal $M$ such that there are infinitely many $n$ with $f(n)=M$, and call such $n$ fat. The key idea is that for any fat $n$, we have $f(a)+f(b) \in \{M,2M\}$ for all $a+b=n$ with $a,b$ sufficiently large (so $f(a),f(b) \leq M$), where we only achieve $2M$ if $a$ and $b$ are fat as well. First, we use the above idea but loosened a bit: let $m$ be the least integer such that $M \mid f(m)$ (which exists, since it's at most the smallest fat number). Then if $n$ is fat and $n-m$ is large, $M \mid f(n-m) \implies f(n-m)=M$. On the other hand, if some $n>k>n-m$ exists such that $f(k)=M$, then $M=f(n) \mid f(k)+f(n-k) \implies M \mid f(n-k)$: impossible by definition, as $n-k<m$. This is enough to imply that the gap between large enough consecutive fat numbers is constant (and equal to $m$). Now, pick positive integers $a,b$, such that $a,b,b-a$ are large enough, and $b$ is fat, so $b+m$ is fat as well. Then $f(b-a)=f(b+m-a)=M-f(a)$. By fixing $a$ and letting $b$ vary, this means that $f$ is eventually periodic (with minimal period $m$). Pick $x$ large and let $1<k=f(mx+1)$, which is constant for large enough $x$. Then by our "general fact", $k$ divides $mx+1,mx+m+1$, which implies that it divides $\gcd(mx+1,mx+m+1)=\gcd(mx+1,m)=1$. Then because there are infinitely many $k$-cool integers, and $1$ is one of them, every positive integer is $k$-cool, completing the proof. $\blacksquare$ Now to tackle the case where $f$ is unbounded. Let $M$ be the minimum value attained by $f$, and call an $n$ such that $f(n)=M$ skinny. Further, let $n$ be powerful if $f(n)\geq f(n-1),f(n-2),\ldots,f(1)$, and overpowered if the inequality is strict, so there are infinitely many overpowered (and thus powerful) $n$. It's easy to see that for all overpowered $n$, we have $f(a)+f(b)=f(n)$ for all $a+b=n$, and if $n$ is powerful (but not overpowered) this equality holds so long as both $a$ and $b$ aren't powerful either, and if one is, then both are. Pick some large overpowered $n$ with $f(n)=x$ and $x>9999M$. Then we have $f(m)=x-M \iff f(n-m)=M$ for $m<n$. On the other hand, by our general claim, the set of $a$ such that $x-M \mid f(a)$ is equal to consecutive multiples of some positive integer $k$, including $k$—in particular, the least $m$ with $f(m)=x-M$ is $k$ (important!). On the other hand, if $a<n$, then $2(x-M)\geq x$, so any such $a$ must have $f(a)=x-M$. Hence for $m<n$, $f(m)=x-M \iff m=ck$ where $c$ ranges from $1$ to some arbitrary positive integer (possibly $1$ as well). This means that the skinny integers less than $n$ are evenly spaced out with a gap of $k$ as well. But since $k$ must equal the least $m$ satisfying $f(m)=x-M$ (which is overpowered), we can repeat this argument with a different (larger) choice of overpowered $n$, giving us a different value of $k$, unless $c \leq 1$ always (in which case the gap isn't defined). This means that there is exactly one skinny number $K$, which in turn readily implies that if $n>K$ is overpowered, then $n-K$ is overpowered as well, and they are consecutive (i.e. there is no overpowered number between them). Thus there exists some $1 \leq r \leq K$ such that the overpowered integers which are at least $r$ are precisely those of the form $Kx+r$ for $r \geq 0$. Note that if $f(r)=C$, then $f(Kx+r)=Mx+C$. For any $y$, pick some $x$ such that $Kx+r>y$, so $f(y)+f(Kx+r-y)=f(Kx+r)=Mx+C$. We then also have $$f(y+K)+f(Kx+r-y)=f(K(x+1)+r)=M(x+1)+C,$$so $f(y+K)=f(y)+M$ for all $y$. We are now ready to finish. Pick some $x,y$ and consider the equation $x+(y+cK)=(x+y+cK)$ for all $c \geq 0$. Then, $$f(x+y+cK) \mid f(x)+f(y+cK) \implies f(x+y)+cM \mid f(x)+f(y)+cM \implies f(x+y)+cM \mid f(x)+f(y)-f(x+y).$$Since $f(x+y)+cM$ is unbounded, $f(x)+f(y)=f(x+y)$, hence $f$ satisfies Cauchy and is linear. This clearly implies that $f(1)>1$ divides all values of $f$, so we're done. $\blacksquare$

Assume $f$ is unbounded. We have a sequence $m_1<m_2< \cdots$ where $f(m_i)>f(n)$ for all positive integers $n<m_i$. First, by size stuff, we see that $f(m_i) = f(m_i-k)+f(k)$ for every positive integer $k<m_i$. Likewise $f(m_i) = f(m_i-k-1)+f(k+1)$. So, $f(m_i)-f(k)$ divides $f(m_i)-f(k+1)+f(1)$. Thus, $f(m_i)-f(k)$ divides $f(k)-f(k+1)+f(1)$. But $f(m_i)-f(k)$ gets arbitrarily large. So, $f(k)-f(k+1)+f(1)=0$. Thus, $f(n)=n \cdot f(1)$ Assume $f$ is bounded. First, we claim that there exist positive integers $a$, $b$, and $p$ where $\gcd(a,b)=1$ and $p$ divides $f(a)$ and $f(b)$. This follows from the fact that $\text{Im}(f)$ is bounded. If there are $k$ primes dividing elements in $\text{Im}(f)$ then just consider a set of $k+1$ pairwise relatively prime positive integers, by PHP we get what we want. Now, let $A=\{a_1<a_2< \cdots \}$ be the set of positive integers where $f(a_i)$ is divisible by $p$. We claim $a_k = c \cdot k$ for some positive integer $c$. Indeed, if $m>n$ are positive integers then $f(a_m)$ divides $f(a_m-a_n)+f(a_n)$. Since $p$ divides $f(a_m)$ and $f(a_n)$, it must follow that $p$ divides $f(a_m-a_n)$. So, $a_m-a_n \in A$. Now, we will proceed by induction. Suppose $a_i = c \cdot i$ for every positive integer $i<k$, we will show $a_k = c \cdot k$. Assume $a_k < c \cdot k$. Then, $a_{k}-a_{k-1}<k = a_1$. But this contradicts minimality since $a_k-a_{k-1} \in A$. Now, assume $a_k > c \cdot k$. Then $a_k>a_k-a_1>a_{k-1}$. But because $a_k-a_1\in A$, this implies there is an element in $A$ between two consecutive elements. Contradiction. So, we have positive integers $\gcd(a,b)=1$ where $p$ divides $f(a)$ and $f(b)$. But, this implies that $a = k \cdot A$ and $b = k \cdot B$ for some $A$ and $B$. So, $k=1$. Implying that $p$ divides $f(n)$ for all positive integers $n$.

).

Assume for contradiction that there exists large $N$ such that for $n \ge N$, $\gcd(f(1), f(n))=1$. Claim: $f$ is unbounded. Proof. First, we note that $\gcd(f(1), f(n+1)) \mid \gcd(f(1), f(n))$ for all $n$, and inductively we have \[ \gcd(f(1), f(a)) \mid \gcd(f(1), f(b)) \]whenever $a > b$. Furthermore, for such $a, b$, it follows by the Euclidean algorithm that \[\gcd(f(a), f(b)) \mid \gcd(f(a-b), f(b)), \]and we can accordingly condense this to \[ \gcd(f(a), f(b)) \mid \gcd(f(1), f(n)) \mid f(1) \]for some $n$. By our assumption, when both $a$ and $b$ are larger than $N$, $\gcd(f(a), f(b)) \mid 1$, which forces $\gcd(f(a), f(b))=1$, implying that $f$ is unbounded. We assume the claim henceforth. Say that a positive integer $n$ is Skywalker if and only if $f(n) \ge f(k)$ for each $k < n$; clearly there is an infinitude of such numbers. By definition $f(n)=f(k)+f(n-k)$ for all $k<n$ whenever $n$ is Skywalker. Let $n$ be an arbitrarily large Skywalker, and $m<n$ be arbitrary. Fixing $m$ and variating $n$, the original functional equation implies \[ f(n-m+1) \mid f(n-m)+f(1), \]which we easily reduce to \[ f(n) - f(m) \mid f(m)-f(m-1)-f(1), \]so by size reasons we have $f(m)-f(m-1)-f(1)=0$, which rewrites as $f(m)=f(m-1)+f(1)$. Inductively we have $f(i)=if(1)$ for all $i \ge 1$, but this is a contradiction to our initial assumption that $\gcd(f(1), f(n))=1$ for sufficiently large $n$. We conclude. Remark: This proof consists of three main components, namely showing that $f$ is unbounded by following the Euclidean algorithm, defining Skywalker numbers using the unboundedness of $f$ and observing their infinitude, and solving the functional equation by fixing some $m<n$ (where $n$ is a large Skywalker) and variating $n$. In fact, the final two steps are motivated by the solution to 2019 N4, in which the functional divisibility is taken to advantage by fixing the dividend and varying the divisor enough to conclude that the dividend is 0.

I was suggested to solve this by Leo.Euler; here's a long and inefficient solution, where I just threw things at the wall until it stuck: Suppose FTSOC that there exists a number $L$ (we take the smallest) that does not share the common gcd of the numbers smaller than it; let the earlier common gcd be g. Let $d_n=\gcd(f(n),f(1))$. Note that $$d_{n+1}=\gcd(f(n+1),f(1))\mid\gcd(f(n)+f(1),f(1))=d_n\stackrel{\text{induction}}{\rightarrow}d_i\mid d_j\forall i>j\implies\forall l\ge L,d_l\mid d_L,$$and by assumption $\gcd(d_L,g)=1\implies\gcd(d_l,g)=1$. We also extract $$\forall a\equiv1\pmod b,a,b\ge L,\gcd(f(a),f(b))\mid\gcd(f(a-b)+f(b),f(b))=\gcd(f(a-b),f(b))=...=\gcd(f(1),f(k))\mid f(1)$$by iterating. By assumption, this is one (otherwise $1<\gcd(f(a),f(b),f(1))\mid\gcd(f(a),f(1))$); in particular, f is unbounded. Since f is unbounded, there are an infinite number of times when a new largest value appears in the sequence (namely $f(n)>f(k)\forall k<n$); namely $f(n)>\max(f(k),f(n-k))>\frac{f(k)+f(n-k)}2\implies f(n)=f(k)+f(n-k)$ for infinite n. Fix $m$ and vary n with this property; we have $$f(n)-f(m)=f(n-m)\mid f(n-m-1)+f(1)=f(n)-f(m+1)+f(1)\leftrightarrow f(n)-f(m)\mid f(m)-f(m+1)+f(1),$$which for sufficiently large f(n) s.t. LHS>RHS, we must have RHS=0; in particular, $f(m+1)=f(m)+f(1)\implies f(m)=mf(1)$, contradiction since f(1)>1 and f(1) is a common gcd, so our inital FTSOC was wrong.

Fun problem! Sketch: Case 1: IM(f) is unbounded The idea is to look at a "peak" and do some sort of downward induction to get $f(x)=xf(1)$. Case 2:Im(f) is bounded Here, the idea is to take the set of primes dividing $f$ infinitely many times, then prove one of them divides all by contradiction argument.

We begin by solving the case where $d = f(1)$ is the minimum value attained by $f$. In particular, we prove that $d$ divides all values of $f$. Assume the contrary. Then, obviously $f$ is nonconstant. Notice that $d \mid f(x)$ implies $d \mid f(x-1)$ since $d \mid f(x) \mid f(x-1)+f(1) = f(x-1) + d$. Consequently $d$ doesn't divide $f(k)$ for all sufficiently large values of $k$. Now suppose $x \in \mathbb{N}$ satisfies $f(x) \leq f(x+1)$. Then, the condition implies that $f(x+1) \mid f(x) + f(1) \leq 2f(x+1)$. Since equality holds only if $d=f(x)=f(x+1)$, this tells us that either $f(x+1)=f(x) + d$ or $f(x+1)=d$. Consider the smallest positive integer $k$ such that $f(k) \neq kd$. Suppose that a positive integer $x$ satisfies $d \neq f(x) \leq f(x+1) \leq \dots \leq f(x+k)$. Then, the condition implies that $f(x) + kd = f(x+k) \mid f(x) + f(k) \implies f(x + k) \mid f(k) - kd$ and hence $f(x+k) \leq |f(k)-kd|$ which is a constant number. On the other hand, suppose that $x \in \mathbb{N}$ satisfies $f(x) > f(x+1)$. Then, we have $f(x+1) \mid f(x) + d \implies f(x+1) \leq \frac{f(x)+d}{2}$. It is clear that these observations are enough to conclude that $f$ is bounded. (Actually, this implies that if $f$ is unbounded we must have $f(x)=dx$.) Let $\alpha$ be the largest value that appears infinitely many times in $f$. Let $\alpha_1, \alpha_2, \dots$ be the numbers mapped to $\alpha$ by $f$. Consider two sufficiently large positive integers $i > j$ such that $i-j$ is also very large. Then, we have $f(\alpha_j) \geq f(\alpha_j-1)$ and hence $f(\alpha_j-1) = \alpha - d$. The condition implies that $f(\alpha_i) \mid f(\alpha_j-1) + f(\alpha_i-\alpha_j+1)$. Since $i-j$ is very large, we have $f(\alpha_i-\alpha_j+1) \leq \alpha \implies f(\alpha_j - 1) + f(\alpha_i - \alpha_j +1 ) < 2 \alpha$. Hence, $f(\alpha_j-1) + f(\alpha_i-\alpha_j+1) = \alpha \implies f(\alpha_i-\alpha_j+1) = d$, a contradiction. (We actually dont use the fact that $f(1)$ is the minimum here.) $\square$ Now we solve the general case. Let $c$ be the smallest positive integer such that $f(c) \leq f(k)$ for all $k \in \mathbb{N}$. Consider the function $g : \mathbb{N} \to \mathbb{N}$ such that $g(x) = f(cx)$. Observe that $g(m+n) \mid g(m) + g(n)$ for all $m, n \in \mathbb{N}$ and $g(1) \leq g(k)$ for all $k \in \mathbb{N}$. It follows that $g(1) \mid g(k) \Leftrightarrow f(c) \mid f(ck)$ for all positive integers $k$. Case 1: The sequence $f(c), f(2c), \dots$ is bounded. It suffices to show that $f$ is bounded. Assume the contrary. Then there exists a positive integer $s$ such that the sequence $f(s), f(c+s), f(2c+s), \dots$ is unbounded. Let $f(ck+s)$ be a sufficiently large term of this sequence. Our condition implies that $f(ck+s) \mid f(ck) + f(s)$ which is bounded by a constant number, a contradiction. $\square$. Case 2: The sequence $f(c), f(2c), \dots$ is unbounded. Note that $f(ck)=kf(c)$. We claim that $f(x+c) = f(x) + f(c)$. Using the same logic as Case 1, we see that the sequences $f(s), f(c+s), f(2c+s), \dots$ are unbounded for all positive integers $s$. Consider positive integers $k$ such that $f(ck+s) > f(ck_0+s)$ for all $k > k_0$. Suppose that $f(ck) > f(ck+s)$. Consider the largest positive integer $\alpha \leq k$ such that $f(c\alpha) \leq f(ck+s)$. It is clear that $f(ck+s) - f(c\alpha) < f(c)$ The condition implies that $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s)<2f(ck+s)$. Hence, $f(c(k- \alpha)+s) < f(c)$ a contradiction. Then, $f(ck+s) \mid f(c\alpha) + f(c(k-\alpha)+s) < 2f(ck+s)$ implies that $f(c(k-\alpha)+s) + \alpha f(c) = f(ck+s)$. Now we prove that $f(x+y)=f(x)+f(y)$. Let $x=\alpha c+ x_0$ and $y=\beta c + y_0$. Then, $f(x+y)=(\alpha+\beta)c+f(x_0+y_0) \mid f(x) + f(y) = c(\alpha+\beta) + f(x_0) + f(y_0)$ and hence $c(\alpha+\beta)c + f(x_0 + y_0) \mid f(x_0) + f(y_0) - f(x_0+y_0)$ for all positive integers $\alpha$ and $\beta$. This implies $f(x_0) + f(y_0) = f(x_0+y_0) \implies f(x) + f(y) = f(x+y)$. Hence, $f(x) \equiv kx, \ k \in \mathbb{N}$. $\blacksquare$

Claim: if $c|f(a),c|f(b)$ then $c|f(gcd(a,b))$ Proof: Its easy to see $c|f(a),c|f(b) \implies c|f(|b-a|)$ use euclidian division algorithim to prove the claim . Case 1: $f$ is bounded above or in other words $f$ attains finite values. Let $f(M)=t$ be the largest value in its range which repeats infinitely often. say $a$ is the smallest natural number such that $f(a)=t$ . we know then that $f(x)=t \implies a|x$ Claim: $f(x)=t \iff a|x$ for large $x$ assuming $n$ is large we have $f(n)|f(a)+f(n-a)$ if $f(n)=t$ we know $f(n-a)=t$ using this the claim is easy to see . Claim: For large $x$ , $f(x)=t$ or $\frac{t}{2}$ Consider the sequence $t=f(ax_1)=f(a(x_1+1))=......$ where $x_1$ is large covering all large solutions for $f(x)=t$ Now for any large $m$ not divisible by $a$ pick some large $n$ such that $m+n=ax_1$ Now its easy to see $I=f(m)=f(m+a)=f(m+2a)=........$ we know then $|$ divides $t$. Pick any other large $m_1$ such that $a|m+m_1$ and choose some large $n_1$ such that $a|m_1+n_1$ to similarly get $a|f(m_1)$ and repeat similarly from here observe we are writing $t$ as a sum of its divisors only way to do is $\frac{t}{2}+\frac{t}{2}$ Now once we have the main problem proved for large $x$ , smaller $x$'s automatically follow pretty easily . Case 2: $f$ is unbounded . Its easy to observe $f(2^d)|2f(2^{d-1})|4f(2^{d-2})......|2^df(1)$ now i define the function $f_2(x)=$ largest odd factor of any natural no $x$ , observe $f_2(2^{d+1})|f_2(2^{d})$ Case 1: $f_2(f(2^d)) > 1$ always . Prove that the common odd factor divides any number of form $f(K 2^t)$ where $K$ is a odd no. By induction. Case 2: The sequence $f(1),f(2),f(4),.....$ eventually turns into powers of 2 . Say $f(2^d)$ is the smallest power of $2$ in the sequence . Claim: All multiples of $f(2^d)$ come in the sequence $f(2^d),f(2^{d+1}),f(2^d*3),f^(2^{d+2}),.....$ appolozie my laziness prove alll terms basically are multiples of $f(2^d)$ and do $f^(2^d+2^dt)|f(2^d)+f(2^dt)$ , its easy prove that the sequence wont be bounded . which will give u this claim . Now observe $f^(2^dx+r)|f(2^dx)+f(1)$ where $f(1)$ is odd Now as $f(1)$ has to be odd[can be proved with more that if it wasent the case all terms would be even]. , we know there exist ifninitely many $x$ such that $f(2^dx)+f(1)$ is a power of $f(1)$ , by which the result isnt hard to see[ too lazy to add the details ]

Lets prove that $f$ is bounded. If we assume that $f$ is unbounded we can say that there are infinite amount of $N$ that $f(N)$ is the prefix max. So it becomes that for any $x < N$ $f(x) + f(N - x) = f(N)$. Now if we take large N and some x to be $f(N - x) | f(N - x - 1) + f(1)$ and it becomes that $f(N) - f(x) | f(N) - f(x + 1) + f(1)$ which in turn means that $f(x + 1) = f(x) + f(1)$ so $f(x) = xf(1)$. Now that $f$ is bounded we can assume that there is a set of values of $f$ lets call $A$ that they appear infinitely many times in $f$. It is clear that the $\gcd(f(n), f(1))$ divides all $f$ less than $n$. If we use euclidean alg on $f$ we can easily see that the $\gcd(f(x), f(y) | f(\gcd(x, y))$. So it means that every occurrence of a element of $S$ is divisible by some "primitive occurrence". And if that occurrence is $1$ we will get that that element of $S$ is divisible by $f(1)$ in turn all of $f$ will be divisible. So every "primitive" occurrence divides every occurrence of elements of $S$. Every $f(x)$ if $x$ is large will be an element of $S$ which means that every $x$ will be divisible by some "primitive" occurrence but we can take an $X$ that isn't divisible by any so thus a contradiction.

woah this is like the most perfect number theory FE ever made We split into two cases. Case 1: $f$ is bounded, say by $N$. Then there exists a nonempty set of positive integers $S$ such that for any $k \in S$, $k \mid f(n)$ for infinitely many values of $n$. Otherwise, every $k$ only divides $a_k$ values of $n$, and we can only define $f$ for less than $a_1+a_2+\cdots+a_N$ values of $n$. For each $n \in S$, let $m_n$ be minimal such that $n \mid f(m_n)$, and let $a_1$ be the minimum among the $m_n$. Furthermore, let $a_2, a_3, \dots$ be the values with this $n \mid f(a_i)$ in increasing order. Claim: For any $q \in \mathbb N$, $n \mid f(qa_1)$. Proof: Observe we have \begin{align*} f(a_i) \mid f(a_i - a_1) + f(a_1) &\implies n \mid f(a_i - a_1) \\ f(a_i - a_1) \mid f(a_i - 2a_1) + f(a_1) &\implies n \mid f(a_i- 2a_1) \\ &\vdots \end{align*}so we inductively have $n \mid f(a_i \bmod a_1)$. If $a_1 \nmid a_i$, this is less than $a_1$, hence we must have $a_1 \mid a_i$. By definition, the sequence $\{a_i\}$ has infinitely many terms, so for any $q$, we can find a $a_\ell > qa_1$, and the above process implies $n \mid f(qa_i)$, as needed. $\blacksquare$ Claim: $a_1 = 1$. Proof: Otherwise, any divisor $d$ of $f(1)$ divides only finitely many $f(n)$. In particular, for sufficiently large primes $p$, $f(p) \mid f(1) p$ implies $f(p) = p$. But this contradicts $f$ bounded. $\blacksquare$ These two claims solve the bounded case. Case 2: $f$ is unbounded. Then by definition, there exists a sequence $n_1, n_2, n_3, \dots$ such that $f(n_i) > f(k)$ for all $k < n_i$. For these $n_i$, we must have $f(n_i) = f(k) + f(n_i-k)$ as $2f(n_i) > f(k) + f(n_i-k)$ for all $k$. In particular, we have the following claim: Claim: $f(k+1)-f(k) = c$ for some constant $c$. Proof. We will show that $f(k) - f(k-1) = f(k+1) - f(k)$ for each $k$. Take some $n_i > k$; by the previous property, \[f(k) + f(n_i-k) = f(n_i) = f(k+1) + f(n_i-k-1) \implies f(k+1) - f(k) = f(n_i-k) - f(n_i-k-1).\]Let $a_{k-1} = f(k) - f(k-1)$ and $a_k = f(k+1) - f(k)$. We have \[f(n_i-1) \mid \gcd(f(k-1) + f(n_1 - k), f(k) + f(n_1-k-1)) = \gcd(f(k-1)+f(n_1-k), a_{k-1}-a_k).\]In particular, $f(n_i - 1) \mid a_{k-1} - a_k$. But $\{f(n_i)\}$ is unbounded, hence $\{f(n_i - 1)\} = \{f(n_i) - f(1)\}$ is unbounded, so $a_{k-1} = a_k$, as needed. $\blacksquare$ Therefore $f$ is linear in $n$. Let $f(1) = b$ and $f(2) = a+b$; if $a$ and $b$ are relatively prime, then $a+b \mid 2b$, which is a clear contradiction as $\gcd(a+b, 2b) = \gcd(a+b, 2)$. Hence $a$ and $b$ share a common factor $d$, and this $d$ divides $f(n)$ for every $n$.