Say a number is large if it is positive and exceeds $M$. Also for brevity let $g = f^r$. Note that if $f$ has a large fixed point $x$, then $x = g(x) = ax + b > x$, contradiction. So henceforth assume that $f$ has no large fixed points. Also, note $f$ is injective. A chainsaw is a sequence $x_0 \to x_1 \to x_2 \to \dots$ of large numbers such that $f(x_{i-1}) = x_i$. Claim: There exists an infinite chainsaw. Proof. We prove first by induction on $n$ that we can get a finite chainsaw $x_0 \to \dots \to x_n$. For $n=0$ this follows by taking $x_0$ large. For $n \ge 2$, suppose we have $x_0 \to \dots \to x_n$, and let $y = f(x_n) \ge 0$ be nonnegative but not necessarily large. First we claim it is not the case that $y=b=0$ (ruling out a silly edge case). Otherwise, $f(ax_n+b) = ay+b = 0$, but $ax_n+b > x_n$ contradicting injectivity. Then note that $g(x_0) \to \dots \to g(x_n)$ is a chainsaw as well, with $f(g(x_n)) = ay+b = g(y)$. Thus replace $x_0$ with $g(x_0)$, et cetera, and $y$ with $g(y)$. By repeatedly applying $g$ in this way, we can eventually make $y$ large. Now note that if we have a chainsaw of with more than $r$ terms, then it extends naturally to an infinite chainsaw, according to the recursion $x_k = ax_{k-r} + b > x_{k-r} > M$. Thus there exists an infinite chainsaw. $\blacksquare$ We fix any particular infinite chainsaw $x_0 \to x_1 \to \dots$ now. We are going to show that this chainsaw alone implies the problem (in fact it will turn out the chainsaw must correspond to repeated applications of a linear polynomial). For brevity, let $y_i = g(x_i) - x_i$. Consider a large integer $k$ and note that the third condition implies that \begin{align*} {\mathbb Z} &\ni \frac{f(g^k(x_1))-f(x_0)}{g^k(x_1)-x_0} = \frac{g^k(x_{2})-x_{1}}{g^k(x_1) - x_0} \\ &= \frac{a^k x_2 + b(1+\dots+a^{k-1}) - x_1} {a^k x_1 + b(1+\dots+a^{k-1}) - x_0} \\ &= \frac{[(a-1)x_2+b] a^k - [(a-1)x_1+b]} {[(a-1)x_1+b] a^k - [(a-1)x_0+b]} \\ &= \frac{y_2 a^k - y_1}{y_1 a^k - y_0}. \end{align*}This function must be an integer for every $k$, but as a sequence of real numbers it approaches the limit $t = y_2 / y_1$. Thus we conclude that the limit $t$ is itself an integer, and also that $y_1 / y_0 = t$ (by picking any large enough $k$). Repeating this argument, there exists an integer $t$ such that \[ t = \frac{y_1}{y_0} = \frac{y_2}{y_1} = \frac{y_3}{y_2} = \dots. \]Thus \[ t^r = \frac{y_r}{y_0} = \frac{g(x_r) - x_r}{g(x_0) - x_0} = \frac{a(ax_0+b)+b-(ax_0+b)}{ax_0+b-x_0} = a \]as desired.

Let $N=M+1$ and $C=N+f(N)$. First we prove that $f(n) \ge n-N$ for $n>C$. We easily see that $f$ is injective, hence $0\neq |f(n)-f(N)| \ge n-N$. Since $n>C$, we get that $f(n)>f(N)$ (remember both $f(n),f(N)$ are non-negative integers) and therefore $f(n) \ge n-N+f(N) \ge n-N$. Now take $n$ large enough, so that $n> C+(r+1)N$, say. Hence all $n,f(n),f(f(n)),...,f^{(r)}(n)$ are greater than $C$.Hence $$an+b=f^{(r)}(n) \ge f(n)-(r-1)N$$Therefore $f(n) \le an+b'$ for $b'=b+(r-1)N$. Finally, lets look again at the divisibilities. We see that $$f(n) \equiv f(N) \mod (n-N)$$$$f(n) \equiv f(N+1) \mod (n-N-1)$$If $f(N)=x$,$f(N+1)=y$, wee see that $f(n) \equiv -x(n-N-1) +y(n-N) \mod (n-N)(n-N-1)$ by CRT. Therefore if we take the constants $u=y-x, v=x(N+1)-Ny$, we have $$f(n)=un+v+k(n-N)(n-N-1)$$for a suitable integer $k$. If we let $n$ be large enough and recall that $an+b' \ge f(n) \ge 0$, we see that the only possible $k$ will be $0$, otherwise one of these two conditions will be false. Hence, there is some $T$ such that $n>T$ implies $f(n)=un+v$. Since $f(n) \ge n-N$, we get $u \ge 1$. So we can take multiple $n$ such that all $n,f(n),f(f(n)),...,f^{(r)}(n)$ are greater than $T$, giving $an+b=f^{(r)}(n)=u^rn+v+vu+...+vu^{(r-1)}$, therefore $a=u^r$.

DVDthe1st wrote: Let $M,a,b,r$ be non-negative integers with $a,r\ge 2$, and suppose there exists a function $f:\mathbb{Z}\rightarrow\mathbb{Z}$ satisfying the following conditions: (1) For all $n\in \mathbb{Z}$, $f^{(r)}(n)=an+b$ where $f^{(r)}$ denotes the composition of $r$ copies of $f$ (2) For all $n\ge M$, $f(n)\ge 0$ (3) For all $n>m>M$, $n-m|f(n)-f(m)$ Show that $a$ is a perfect $r$-th power. Solution. Without loss of generality assume $M$ is positive. Let us first prove a claim: Claim. For any $t\ge 0$ there exist $M_t$ such that $f^t(x)>M$ for all $x\ge M_t.$ Proof. It is clear that $f^n$ is injective for any $n\ge 0, $ and it is easy to see that the claim is true for $t=0,1.$ Assume that $t$ is the minimal natural number such that there exist arbitrarily large $x>0$ with $f^t(x)\le M.$ Let $S$ be the set of positive integers $x$ for which $f^t(x)\le M$, note that for all large $x\in S$ it must follow that $f^t(x)<0$ because of injectivity. So $f^{t-1}(x)<M$ for an infinite subset $S'$ of $S.$ This contradicts the minimality of $t.$ Hence the claim. $~\square$ Let $K=\max\{M_0,M_1,\ldots,M_r\}$ so we have that $$m-n\mid f(m)-f(n)\mid f^2(m)-f^2(n)\mid \cdots\mid f^{r-1}(m)-f^{r-1}(n)\mid a(m-n)$$for all $m>n>K.$ Observe that $f(an+b)=f(f^r(n))=f^r(f(n))=af(n)+b.$ Putting $m=an+b$ we obtain that $$n(a-1)+b\mid f(n)(a-1)+b\mid a((a-1)n+b),$$which implies that $$f(n)=g(n)n+\frac{b(g(n)-1)}{a-1}$$where $g$ is a function from $\{K+1,K+2,\ldots\}$ to the set of positive divisors of $a.$ Notice that $f(n+1)-f(n)\mid a$ for all $n>K,$ we see that \begin{align*}f(n+1)-f(n)&=g(n+1)n+g(n+1)-ng(n)+\frac{b}{a-1}(g(n+1)-g(n))\\&=g(n+1)+\left(\frac{b}{a-1}+n\right)(g(n+1)-g(n))\end{align*}Hence \begin{align*} a&\ge \left|g(n+1)+\left(\frac{b}{a-1}+n\right)(g(n+1)-g(n))\right|\\ &\ge \left|\left(\frac{b}{a-1}+n\right)(g(n+1)-g(n))\right|-|g(n+1)|\\ &\ge \left(\frac{b}{a-1}+n\right)\left|(g(n+1)-g(n))\right|-a. \end{align*}So we conclude that $g$ is eventually constant. Hence there exist $k,c\in\mathbb{Z}$ where $k\ge 1$ such that $f(n)=nk+c$ for all sufficiently large $n.$ This forces $a=k^r.$ Done. $~~\blacksquare$

I found this problem to be quite silly We will a number large if it is larger than $M$. A large number $n>M$ is sad if $f(n)\le M$. The main claim is : Claim: There exists an infinite sequence of large numbers $(x_0, x_1, x_2, \dots)$ such that $x_{i+1} = f(x_i)$ for all $i\ge 0$. Proof: First, observe that $f$ is injective and has no fixed points. Hence there are at most $M+1$ large sad numbers. Let $n$ be any big number, and consider the sequence $$S = (n, f(n), f^2(n), f^3(n), \dots),$$ Note that since it has the following subsequence : $$(n, f^r(n), f^{2r}(n), \dots) = (n, an+b, a(an+b)+b, \dots)$$Thus, $S$ contains arbitrarily many large numbers, and by injectivity every number in $S$ is distinct. If $S$ does not contain any sad numbers, then we can just take $S$ as our sequence. Otherwise, let $k$ be maximal with $f^k(n)$ bad. Then let $s$ be large with $rs > k$ . We consider the sequence : $$(f^{sr}(n), f^{sr+1}(n), f^{sr+2}(n), \dots).$$ This works because $f^{sr}(n) = a^sn+(a^{s-1}+\dots+a+1)b > M$ is large and none of the numbers in the sequence are sad by our choice of $s$. This proves the claim. $\blacksquare$ Now take a sequence $(x_0, x_1, x_2, \dots)$ satisfying the condition in the claim. Now the problem has been reduced to a standard divisibility problem . We have $$x_{i}-x_{i-1}\mid x_{i+1}-x_i \quad \text{and} \quad x_{i+1}-x_{i-1}\mid x_{i+2}-x_i$$for all $i\ge 1$. We write $y_i = x_i - x_{i-1}$ and $q_i =\frac{ y_{i+1}}{y_i}$ so that the conditions become $y_i\mid y_{i+1}$ and $y_i+y_{i+1}\mid y_{i+2}+y_{i+1}$. Claim : $(q_i)$ is periodic with period $r$ . Proof: Note that $$y_{i+r} = x_{i+r} - x_{i+r-1} = (ax_i+b)-(ax_{i-1}+b) $$So we have $$q_{i+r}= \frac {y_{i+r}}{y_{i+r-1}} = \frac{ay_{i+1}}{ay_i} = q_i.$$ So the claim stands proven .$\blacksquare$. Next , write : $$ y_i+y_{i+1}\mid y_{i+1}+y_{i+2} \implies y_i+y_{i+1}\mid y_{i+2}-y_i $$$$\implies 1+q_i \mid \frac{y_{i+2}}{y_i}-1 $$$$\implies 1+q_i \mid \frac{y_{i+2}}{y_i}-1 - \frac{y_{i+2}}{y_{i+1}}\left(1+\frac{y_{i+1}}{y_i}\right) = -1-\tfrac{y_{i+2}}{y_{i+1}} $$$$\implies 1+q_i \mid 1 + q_{i+1}.$$ However this means: $$1+q_i\mid 1+q_{i+1}\mid \dots \mid 1+q_{i+r} = 1+q_i$$Hence $(q_i)$ is constant, say equal to $q$. Then$$a =\dfrac { y_{i+r}}{y_i} = q_iq_{i+1}\dots q_{i+r-1} = q^r,$$as desired. We are done$\blacksquare$

The main motivation is that $n-m\mid f(n)-f(m) \mid f^2(n)-f^2(m) \mid \cdots \mid f^r(n)-f^r(m)=a(n-m)$. Claim: there exist $x$ such that $f^k(x)>M$ for all $0\le k\le r-1$. Proof. Note $f^m(an+b)=f^m(f^r(n))=f^r(f^m(n))=af^m(n)+b$, so it suffices to prove the result for $\frac{M-b}{a}$. Repeating this process eventually gives $M<0$ as $a\ge 2, b\ge 0$, which is clear as $f(n)\ge 0\forall n\ge M$. Take such $x$. Let $q_k=\frac{f^{k+1}(x)-f^k(x)}{f^k(x)-f^{k-1}(x)}$, then observe $q_k=q_{k+r}$ and $\prod\limits_{k=0}^{r-1} q_k=a$. Then, $f^{k+1}(x)-f^k(x)=(f(x)-x) q_1q_2\cdots q_k$. Note $f^k(x)-x\mid f^{k+1}(x)-f(x)$, so $1+q_1+q_1q_2+\cdots + q_1q_2\cdots q_{k-1} \mid q_1(1+q_2+q_2q_3+\cdots+q_2q_3\cdots q_k)$ Note $\gcd(q_1, 1+q_1+q_1q_2+\cdots + q_1q_2\cdots q_{k-1})=1$, so $1+q_1+q_1q_2+\cdots + q_1q_2\cdots q_{k-1}\mid 1+q_2+q_2q_3+\cdots+q_2q_3\cdots q_k$. Let $f(n,k) = 1+q_n+q_nq_{n+1} + \cdots + q_nq_{n+1}\cdots q_{n+k-1}$. We've shown that $f(n,k)\mid f(n+1,k) \mid f(n+2,k) \mid \cdots \mid f(n+r,k)=f(n,k)$. Therefore, $|1+q_1+q_1q_2+\cdots + q_1q_2\cdots q_{k-1}| = |1+q_2+q_2q_3\cdots + q_2q_3\cdots q_k|$ This implies $q_i\in \{-X-1, X-1\}$ for some integer $X$. Clearly, $X>0$, and $X=1$ easily implies $q_i=2\forall i$ since $f^r(m)\ne f^r(n)$, so $f(m)\ne f(n)$. Hence assume $X\ge 2$. If $k=2, q_1=-X-1, q_2=X-1, $ then $a=1-X^2$ is at least 2, contradiction. If $k>2,$ then we can see if $q_i=X-1, q_{i+1}=-X-1, |1+q_i(q_{i+1}+1)|=|1+(X-1)(-X)|=X^2-X-1$ If $q_i=-X-1, q_{i+1}=-X-1, |1+q_i(q_{i+1}+1)|=|1+(-X-1)(-X)|=X^2+X+1$ If $q_i=X-1, q_{i+1}=X-1, |1+q_i(q_{i+1}+1)|=X^2-X-1$ If $q_i=-X-1, q_{i+1}=X-1, |1+q_i(q_{i+1}+1)|=|1+(-X-1)X|=|-X^2-X+1|=X^2+X-1$. For $X\ge 2,$ note the four outcomes are totally different, so it follows $(q_i,q_{i+1})$ is a constant pair, which easily implies $q_i=q_{i+1}$, as desired.

Easy for Q3? By (1) , $f$ is injective. Let $t = M+1, s = t+f(t)$. For $n>s$ we have $n-t | f(n) - f(t)$. If $f(n)<f(t) \implies |n-t|\leq |f(n)-f(t)|\leq |f(t)|<|n-t|$ which is not possible . Hence $f(n)>f(t)$ . Define $$g(n) = \dfrac{f(n)-f(t)}{n-t} \hspace{0.25cm}\text{ for } n>s$$Note that $g(n)>0$ for all $n>s$, now we have two cases . Case 1 - $g(n)$ takes some value $c$ infinitely many times for $n>s$. Let $n>m>t$ such that $g(n)=c$, so $f(n) = cn + f(t)-ct$. We have $n-m | f(n) - f(m) \implies n-m | cn - ct +f(t)-f(m) \implies n-m | cm -ct +f(t)-f(m)$. But $n$ can be as large as we want . Hence $cm -ct +f(t)-f(m) = 0 \implies f(m) = cm+k $ for $m>t$. Now for large enough $m$ we would have $f^{r}(m) = c^rm + k'$ and hence $a = c^r$. Case 2- Case 1 is not true . Let $c$ be such that $c^r > a$, as $g$ takes all values less than $c$ only finitely many times, we have a $N$ such that for $n>N, g(n)>c$. And hence for $n>N, f(n) > cn+f(t)-ct = cn +k' = h(n)$. Now as $c>1$ there exists a $P$ such that for $n>P, h(n)>n$. Now take any $n>P,N \implies f(n)>h(n)>n>N \implies f(f(n))>h(f(n))>h(h(n))>n>N$ and we continue till we get $f^r(n)>h^r(n)$. Hence $an+b > c^rn +l$ for all large enough $n$, but this is clearly false as $a<c^r$. Hence proved.

By the first condition we have $f$ is injective. Hence for $(M, +\infty)$, there are only finitely many (at most $(1+M)^r$) number of $n$ such that $\min \{n, f(n), f(f(n)), \dots, f^{(r)}(n)\} \le M$. Call a number $n$ large if all of $n, f(n), \dots, f^{(r)}(n)$ are larger than $M$. Then there are infinitely many large number. For any pair of large number $n \neq m$, we have \[n-m \mid f(n)-f(m) \mid \cdots \mid f^{(r)}(n) - f^{(r)}(m) = a(n-m)\]Hence $f(n) - f(m) = k(n-m)$ for some $k \mid a$, which has only finitely possibilities. Fix a large number $n$. By pigeon hole, there is a $k$ such that $f(n)-f(m) = k(n-m)$, or $f(n) - kn = f(m) - km$, for infinitely many $m$. Let $f(n)-kn = c$. Then there are infinitely many $m$ with $f(m) = km+c$. For any $r>M$, by the third condition, $m-r \mid f(m) - f(r)$, replace $f(m)$ by $km+c$ we have \[m-r \mid rk+c-f(r) \]holds for infinitely many $m$. So $f(r) = kr+c$ for all $r>M$. So now for any large number $n$ we have $$ an+b = f^{(r)}(n) = k(f^{(r-1)}(n))+c = \cdots = k^rn + c(1+k+k^2+\cdots k^{r-1})$$Since there are infinitely many large number $n$, we conclude that $a = k^r$, as desired.

This was rather easy for a China P3 Consider the obvious directed graph induced by $f$. It's acyclic since $a > 1$ and graph is also injective, since $f(x) = f(y) \implies ax+b = f^r(x) = f^r(y) = ay + b \implies x = y$ So the graph is just a bunch of disjoint chains. Let $S$ denote the set of numbers that is $b \pmod a$. From the $r$th term onwards, the chains have only elements of $S$ Furthermore, exactly $r-1$ terms in each chain are not in $S$ and every term after that is. Since there are infinitely many numbers not in $S$, there are infnitely many chains. Now, ignore any chain which contains a positive number $\le M$, we still have infinitely many chains, and infinitely many of them contain big positive numbers. Since $f(n) \ge 0$ for $n$ sufficiently big, we have that such a chain has all numbers $> M$ Henceforth, when variables are used, assume that they're all $> M$ Now, see that we have $an+b-n | f(an+b) - f(n) = af(n) + b - f(n)$ So $f(n) = nk + k \left(\frac{b-1}{a-1}\right)$, so we have that for some constants $c,d$, we have $cn + d | f(n)$ and let the ratio be $k_n$ Now, note that $z | f(n+z) - f(n) \implies z | d(k_{n+z} - k_n)$ Now, note that since $f$ is increasing, we must have $ck_n \le a$ since otherwise $f^r(n) > an+b$, in particular, $k_n$ is bounded Pick $z$ to be a sufficiently large prime and since $k_n$ is bounded, we have that $k_{n+z} = _n$, picking $z$ instead to be another different sufficiently large prime, we get that $k_n$ is just constant for sufficiently large values. Now just pick a chain with only sufficiently large values, we have that $f^r(n)$ has its coefficient of $n$ as $(ck_n)^r = a$, meaning $a$ is a perfect $r$th power, as desired. $\blacksquare$

Replacing $n$ by $f(n)$ in $(1)$ gives $$ f(an + b) = af(n) + b ~~ \forall ~ n \in \mathbb Z \qquad \qquad (4) $$Replacing $n$ by $am + b$ in $(3)$ gives $$ (a-1)m + b \mid af(m) + b - f(m) = (a-1)f(m) + b ~~ \forall ~ m > M \qquad \qquad (5) $$$(5)$ in fact gives $f(m) \ge m ~ \forall ~ m > M$ (here we use $f(m) \ge 0$). Let $$ x_m := \frac{(a-1)f(m) + b}{(a-1)m + b} \ge 1 ~~ \forall ~ m > M $$Observe $$ \prod_{i=0}^{r-1} x_{f^i(m)} = \frac{(a-1)f^r(m) + b}{(a-1)m + b} = \frac{(a-1)(an + b) + b}{(a-1)m + b} = a \qquad \qquad (6) $$ Claim: Sequence $x_{M+1},x_{M+2}, \ldots$ is eventually constant. Proof: Fix $m > M$ and pick a large $n > M$. We will show $x_n = x_m$. Using $1 \le x_m,x_n \le a$ we obtain \begin{align*} n - m \mid f(n) - f(m) \implies (a-1)(n-m) \mid (a-1)(f(n) - f(m)) \\ \implies \left( (a-1)n + b \right) - \left( (a-1)m + b \right) \mid x_n \left( (a-1)n + b \right) - x_m \left((a-1)m + b \right) \\ \implies \left( (a-1)n + b \right) - \left( (a-1)m + b \right) \mid (x_n-x_m)((a-1)m + b) \end{align*}Now if $x_n - x_m \ne 0$, then $|x_n - x_m| < a$. Particularly, $$ |(x_n-x_m)((a-1)m + b)| \le a( (a-1)m + b)) \le ((a-1)n + b) - ((a-1)m + b) $$since $n$ large. But that's a contradiction, proving our claim. $\square$ Assume $x_n = c$ for all large $n$. Then $$ n \le f(n) \le f^2(n) \le \cdots \le f^{r-1}(n) $$So putting $m=n$ in $(6)$ would give $$ c^r = a $$Which completes the proof. $\blacksquare$

A chain is a sequence $\mathcal{C}_x=(x, f(x), f(f(x)), \ldots)$ where all terms are larger than $M$. Call an integer $n$ cool if $f(n)\le M$. Claim: There exists an infinite chain. Proof. Notice that $f$ is injective and has no large fixed points from the third and first conditions, respectively, so there are at most $M+1$ cool numbers larger than $M$. Take $n>M$, and note that $S=(n, f^r(n), f^{2r}(n), \ldots)$ is a subsequence of $\mathcal{C}_n$, and since $S$ is an increasing sequence, $\mathcal{C}_n$ contains infinitely many integers larger than $M$. If $\mathcal{C}_n$ has no cool elements, then taking $\mathcal{C}_n$ as our chain finishes. If $\mathcal{C}_n$ has a cool element $f^k(n)>M$ with $k$ maximal, then consider the subsequence $\mathcal{C}_{f^{\ell r}(n)}$, where $\ell = \text{max}(M+1, \lceil \frac{k}{r} \rceil)$. It is not hard to see that this works. Thus we are done. Fix an infinite chain $\mathcal{C}_{x_0}=(x_0, x_1, \ldots)$. By the third condition we readily have \[ x_i-x_{i-1} \mid x_{i+1}-x_i. \]Let \[ y_i := \frac{x_{i+1}-x_i}{x_i-x_{i-1}}. \](This gives us not only that $(y_i)$ is an integer sequence, but also that $1+y_i \mid 1+y_{i+1}$ upon some basic divisibility manipulation -- this will be important later!) Note that \[ y_{i+r} = \frac{x_{i+r+1}-x_{i+r}}{x_{i+r}-x_{i+r-1}} = \frac{(ax_{i+1}+b)-(ax_i+b)}{(ax_i+b)-(ax_{i-1}+b)} = \frac{ax_{i+r+1}-ax_{i+r}}{ax_{i+r}-ax_{i+r-1}} = \frac{x_{i+1}-x_i}{x_i-x_{i-1}} = y_i, \]so $(y_i)_{i \ge 1}$ is periodic with period dividing $r$. Revisiting the divisibilities obtained earlier, note that \[ 1+y_i \mid 1+y_{i+1} \mid \ldots \mid 1+y_{i+r} = 1+y_i, \]which fixes $(y_i)$ to be a constant sequence. Indeed, \[ a = \frac{x_{i+r}-x_{i+r-1}}{x_i-x_{i-1}} = \prod_{j=0}^{r-1} y_{i+j} = y_1^r, \]so we are done.

Not bad for a Chinese 3/6, especially considering that the solution is basically forced given the setup. Define an infinite sequence $x_i = f(x_{i-1})$ for each $i \geq 1$. Claim. We can choose $x_0$ such that $x_i \geq M$ for every $i \geq 0$. Proof. First, I claim we can obtain such a sequence of length at least $r$. Say we are given any sequence of $n$ $x_i$'s such that the first $n-1$ terms exceed $M$. Let $y_i = ax_i + b$ for each $i$, and notice that replacing $x_i$ with $y_i$ for each $i$ still yields a valid sequence. On the other hand, $y_n$ strictly increases under this operation, so we can eventually make $x_n > M$ too. Now, suppose that we have a sequence of length at least $r$; then, using the first condition, we can elongate it infinitely, thus proving the claim. $\blacksquare$ So now we can eliminate $M$ from the problem and actually do the fun part. The key claim is the following: Claim. The sequence $x_i$ behaves linearly: in other words, there exist constants $k, \ell$ such that $x_{i+1} = kx_i + \ell$ for every $i$. Proof. Consider the expression $$R_k = \frac{x_{kr+2} - x_1}{x_{kr+1} - x_0} = \frac{z_2 a^k - z_1}{z_1 a^k - z_0}$$where $z_i = (a-1)x_i + 1$ for each $i$. (This follows by an easy recursive computation.) Notice that by the third condition, $R_k$ is an integer for every $k$. On the other hand, it approaches the limiting value $\frac{z_2}{z_1} = c$ for some $c \in \mathbb Z$. This means that by picking large enough $k$, we must have $\frac{z_1}{z_0} = c$ too. Thus the ratio $\frac{z_{i+1}}{z_i}$ is constant for all $i$, and as a result $$a = \frac{(a-1)x_r + b}{(a-1)x_0 + b} = \frac{z_r}{z_0} = c^r.$$

Claim: $f$ is injective. Proof: If $f(x) = f(y)$, then $ax+ b = ay + b$, so $x = y$. $\square$ Claim: There exists an infinite chain $x_0, x_1, x_2, \ldots, $ of positive integers all greater than $M$ such that $f(x_i) = x_{i+1}$ for all nonnegative integers $i$. Proof: We first show there exists an infinite chain of length $n$ for any nonnegative integer $n$. This is by induction, where the base case $0$ is obvious. Suppose it was true for $0,1,2\ldots, n$. Then consider some chain $x_0, x_1, \ldots, x_n$ that has all numbers greater than $M$ and $f(x_i) = x_{i+1}$ for $0\le i<n$. Let $g(x) = ax + b$. We see that $g^k(x_0), g^k(x_1) , \ldots, g^k(x_n)$ is also an infinite chain for any positive integer $k$. So it suffices to show there exists $k$ with $f(g^k(x_n)) > M$. This is obviously true because $f$ is injective and $g$ is strictly increasing on the positive integers. This completes the induction. Now just take a chain $x_0, x_1, \ldots, x_r$ of everything greater than $M$. We show that the values of $x_{r+1}, x_{r+2},\ldots, $ are all greater than $M$. This is by induction. The base case holds because $x_{r+1} = ax_1 + b$. The inductive step works because $x_{r+k} = a r_k + b > M$. Hence we have a working infinite chain. $\square$ $\square$ Fix an infinite chain $(x_i)$. Let $y_n = (a-1) x_n + b$ for any $n\ge 0$ and $c_n = \frac{y_n}{y_{n-1}}$ for any $n>0$. Note that $c_n$ is an integer. Claim: $y_{n+r} = a y_n$ for any nonnegative integer $n$. Proof: We get $y_{n+r} = (a-1) x_{n+r} + b$, which is $(a-1)(ax _n + b) + b$, which equals $a ( (a-1) x_n + b) = a y _ n$. $\square$ This implies that $c_n = c_{n+r}$ for any positive integer $n$. Claim: $(c_i)$ is nondecreasing. Proof: Fix a positive integer $k$. We will show that $c_k \le c_{k+1}$. We have \[(a-1)(x_k - x_{k-1}) = y_k - y_{k-1} \mid (a-1) (x_{k+1} - x_k) = y_{k+1} - y_k,\]so $c_k - 1 \mid c_kc_{k+1} - c_k = c_k(c_{k+1} - 1)$, which means $c_k - 1 \mid c_{k+1} - 1$ (since $c_{k+1} > 1 $), so $c_k \le c_{k+1}$. $\square$ This implies $(c_i)$ is constant, and $a = c_1^r$.

Firstly, observe that an imediate consequence of relation (3) is that $f$ is injective since $a\ne 0$. Now, we claim the following: Claim: There exist $\lambda, \theta \in \mathbb{Z}$ with $f(x) = \lambda x + \theta$ for all $x > M.$ First we show how the Claim solves the problem. Indeed, if the above is true, then $\lambda$ should be positive because of $(2)$ and injectivity. Therefore, exist a constant $N$ such that for all $x > N,$ we have that $x, g(x), g^{(2)}(x) \dots, g^{(r)}(x)$ are all greater than $M,$ where $g(x):= \lambda x + \theta.$ Then, we conclude $f^{(r)}(x) =g^{(r)}(x) $ for all $x > N$ and so we must have $a ={ \lambda}^r$ and we are done. Now we are going to prove the Claim. At first, note that it suffies that there exists $\lambda, \theta \in \mathbb{Z}$ and an infiinite set of integers $A \subset [M, +\infty)$ such that $f(a) = \lambda a +\theta,~~\forall a \in A$. Indeed, if such set and integers exists, then one can fix any integer $m > M$ and note that one has for any $a \in A:$ $$ m-a \mid f(m) - f(a) \iff m-a \mid f(m) - (\lambda a + \theta) \iff m-a \mid f(m) - (\lambda m + \theta) $$where we used $a \equiv m \pmod {m-a}$ in the last implication; as $A$ is infinite, one concludes from the last realation that $f(m) - (\lambda m + \theta) $ has infinitly many divisors, and so it must be zero and we are done; Finally, we show that indeed such a suitable set $A$ exists. Note that as $f$ is injective, one can take a constant $K$ such that for any $m > K$, none of the integers $0,1, \dots, M$ appear in $ m, f(m), f^{(2)}(m) \dots, f^{(r)}(m);$ now take a positive integer $ m > \max (M, K)$ and then we have by condition (3) and the definition of $K$ that $$f(m) -m \mid f(f(m))-f(m) $$$$ f^{(2)}(m) - f(m) \mid f^{(3)}(m) - f^{(2)}(m) $$$$ \vdots $$$$ f^{(r-1)}(m) - f^{(r-2)}(m) \mid f^{(r)}(m) - f^{(r-1)}(m) $$and therefore one has that modulo $f(m) -m:$ $$ f^{(r)}(m) \equiv f^{(r-1)}(m)\equiv \dots f(m) \equiv m ~~(*)$$and so in particular one has $f(m)-m \mid (a-1)m + b$. Now , as $a\ge 2$, we can take $d:= gcd(a-1,b)$ and let $a-1 = d \alpha, b = d \beta$, where $ \alpha \ge 1$ and $gcd ( \alpha, \beta ) =1; $ the last two observations show that, by invoking Dirichlet's Theorem, there exists an infinite set of positive integers $n$ such that $ \alpha n + \beta$ is a prime. Call $S$ such set. Then, for any $n$ in $S$ one has by $(*)$ that $$ f(n) - n \mid d(\alpha n + \beta \rightarrow f(n) - n = d'i$$where $d'$ is an integer divisors of $d$(possibly being negative) and $i \in \{\alpha n +\beta, 1\}$. To finish note that all of the posibilities for $d',i$ induces a linear function on $n$ with coeficients not depending in $n$; as $S$ is infinite and there are finitely many possibilites to $d',i$, there must exist infinitely many $n \in S$ inducing the same $d',i$ and therefore the same linear function and we are done by our previous work.

Consider the directed graph, clearly we get a number of distinct chains. Clearly there must exist a chain such that its first value $i$ is $>M$. Consider this chain. Clearly from all the values in this chain we get that all values beyond the first $r$ are determined. Thus we can using the $f^r(n)=an+b$, bound the chain such that for any value $i$ in the chain $\vert f(i) \vert$ is always below some linear function as $f(i)\geq 0$. Thus if we consider the line going through $f(n)$ and $f(f(n))$, if we let this line be $g$, we get that for any $i$ in the chain $f(i)\equiv g(i)\pmod{lcm(i-f(n), i-f(f(n)))}$, we can find abitrarily large values such we are forced for size reasons to have $f(i)=g(i)$, so we get from these abitrarily large values that the entire sequence must have $f(i)=g(i)$, which from the definition of $f$ implies that $f^r(n)=a^rn+b$ for some $a$ and $b$.