This problem was proposed by Rodrigo Sanches Angelo from Brazil, rsa365 here at Mathlinks.

Here is a solution given by one of our contestants during training. For convenience let $\mho(n) = S(n)$. Call primes larger than $10^{100}$ to be large and otherwise small. First, sum up both sides to get $$\sum_{1 \leq b < a \leq N} S(f(a) - f(b)) \leq \sum_{1 \leq b < a \leq N} S(a-b)$$ for all natural $N$. Now we will show that for any prime power $p^k$, the number of $f(a) - f(b)$ that are divisible by $p^k$ is at least that of $a-b$ when $N$ is fixed. Let $g(i)$ denote the number of $f(m)$'s which are $\equiv i$ mod $p^k$. Then the number of $f(a)-f(b)$ that are divisible by $p^k$ is simply $\sum \binom{g(i)}{2}$. Since $\binom{n}{2}$ is convex, it is minimized when the $g(i)$ are equidistributed, which is exactly the case for consecutive naturals and we hence conclude. As a result, we have $$\sum_{1 \leq b < a \leq N} S(f(a) - f(b)) \geq \sum_{1 \leq b < a \leq N} S(a-b)$$since both sides is simply the sum of the number of $f(a)-f(b)$ / $a - b$ which are divisible by $p^k$ where $p > 10^{100}$, which implies that equality holds. This also means that equality holds for every inequality we added up, giving us $S(f(a)-f(b)) = S(a-b)$. A simple and boring induction will tell us that for a fixed $a,b$. $f(a) - f(b) = k(a-b)$, in particular $f(n) =kn + f(0)$, where $k$ is some rational number made up of primes less than $10^{100}$. Let $L(n)$ denote the product of small primes dividing $n$. Let $w(n)$ be the maximal $v_p(n)$ where $p$ is a small prime and let $p_n$ denote this prime. Then we have $$v_{p_{f(i)-f(j)}} (f(i) - f(j)) \geq \frac{1}{10^{100}} \log_{10^{100}} L(f(i)-f(j))$$since there are at most $10^{100}$ small primes. Now, if $j$ is small compared to $i$, we have that $\frac{f(i)-f(j)}{i-j}$ is roughly equal to $\frac{f(i)}{i}$. We aim to show that for any $n$, $\frac{f(n)-f(0)}{n} = k$ is bounded. Assume otherwise, then we have that $\frac{f(i)}{i}$ is unbounded and hence there exists arbitrarily large $i$ such that $\frac{f(i) - f(j)}{i - j}$ is large too where $j$ ranges from $0,1,2,\ldots,10^{100}$. Note that $\frac{f(i)-f(j)}{i-j}$ is at least $L(f(i) - f(j))$ and hence the RHS of our inequality can be made to be as large as we want. Let it be at least $C$ for some real. Then since there are at most $10^{100} - 1$ small primes, by pigeonhole, we must have $0 < j_1,j_2, < 10^{100}$ such that $p_{f(i) -f(j_1)} = p_{f(i) - f(j_2)}$. $$p_{f(i)-f(j)}^C | f(i) - f(j_1) , f(i) - f(j_2) \implies p_{f(i)-f(j)}^C | f(j_1) - f(j_2)$$but $C$ can be made to grow as large as we want while $f(j_1) - f(j_2)$ is a non-zero fixed value - a contradiction. Hence $\frac{f(i)}{i}$ is bounded and so is $k$. Now take $i = p$ where $p$ is some large prime. Then $f(p) - f(0) = kp$ where $k$ is a rational number made up of small primes but if $p$ is larger than $10^{100}$, the denominator of $k$ must be just $1$ and hence $k$ is integer. Since $k$ is bounded above, it takes on only finitely many values and hence by pigeonhole, we must have an infinite sequence $a_1,a_2,\ldots$ such that $f(a_i) = ka_i + f(0)$ for some fixed integer $k$. Now, for any natural $j$, let $f(j) = kj + c$ where $c$ is an integer since $f(j),kj$ are integers. Then we have that $f(a_i) - f(j), a_i - j$ share large prime factors and hence $k(a_i - j) + c , k(a_i - j)$ must also share large prime factors. But these primes must divide $c$ and hence if $p > c$, it cannot divide both of them. Hence we have that $kx + c, kx$ are made up of finitely many primes for infinitely many $x$ and hence the equation $x-y = c$ has infinitely many solutions where the prime factors of $a,b$ belong to some finite set. Rewrite each such solution into the form $ax^3 - by^3 = c$ where $a,b$ are cube-free. There are only finitely many such forms and hence by pigeonhole one of them has infinitely many solutions - a contradiction to Thue's theorem. Finally, we have that $f(n) = kn + c$ for some integers $k,c$. Easy to check as long as $k$ have small prime factors, it will satisfy the conditions.

Let $U(n)=\mho(n)$ and $V(n) = \prod_{p_i>10^{100}} p_i^{a_i}$. We claim that $V(f(a)-f(b))=V(a-b)$. Let $S=\{q_1,q_2,...\}$ with $q_1<q_2<...$ such that $q_i=p_i^{a}$ where $p_i$ is a prime greater than $10^{100}$ and $a$ is a positive integer. We will prove, by strong induction on $i$, that $q_i\mid a-b\iff q_i\mid f(a)-f(b)$. For the base case, consider the numbers $f(a), f(a+1),..., f(a+q_1)$. By the Pigeonhole principle, some two are equal $\pmod{q_1}$. Suppose $f(x)\equiv f(y)\pmod{q_1}$ such that $0<|x-y|<q_1$. Note that $1\le U(f(x)-f(y)) \le U(x-y) = 0$, contradiction! Therefore, it follows that $f(a)\equiv f(a+q_1)\pmod{q_1}$, and that $f(a)\not\equiv f(a+j)\pmod{q_1}$ where $0<j<q_1$. This proves the base case. For the inductive step, suppose the claim is true for $q_j$ for $j<i$. We prove it holds for $q_i$. Consider $f(a),f(a+1),..., f(a+q_i)$. Once again, by Pigeonhole some two are equal $\pmod{q_i}$. Suppose $f(x)\equiv f(y)\pmod{q_i}$ and $0<|x-y|<q_i$. Note by the inductive hypothesis, if $q_j\mid x-y$ then $q_j\mid f(x)-f(y)$ since $x-y < q_i$. On the other hand, $q_i\mid f(x)-f(y)$ as well, while $q_i\nmid x-y$. Thus $S(f(x)-f(y))\ge S(x-y)+1$, contradiction! Therefore $f(a)\equiv f(a+q_i)\pmod{q_i}$ and $f(a)\not\equiv f(a+j)\pmod{q_i}$ for $0<j<q_i$. This completes the inductive step. It follows from our induction that $V(a-b) = V(f(a)-f(b))$. WLOG $f(0) = 0$. Next, we claim that $\frac{fx)}{x}$ is bounded; in other words, there is an absolute constant $K$ such that $\frac{f(x)}{x}\le K$. Suppose that it wasn't bounded; in particular, the fraction was arbitrarily large. Let $Q=\prod_{p_i < 10^{100}} p_i$. Note that since $\frac{f(x)}{x}$ is unbounded, so must the fraction $\frac{f(Q^n)}{Q^n}$. For $n$ large, note that $\frac{f(Q^n)}{Q^n}\approx \frac{f(Q^n)-f(j)}{Q^n-j}$. We also have that $\frac{f(Q^n)-f(j)}{Q^n-j} = \frac{g(n, j)}{j}$ where $V(g(n, j)) = 1$ since $\frac{f(Q^n)-f(j)}{g(n,j)} = V(f(Q^n)-f(j)) = V(Q^n-j) = \frac{Q^n-j}{j}$. Because this tends to infinity as $n$ grows large, there exists a prime $p_{n,j}<10^{100}$ such that $v_{p_{n,j}}(g(n, j))\rightarrow\infty$ as $n\rightarrow\infty$. Doing this for enough small $j$ with $V(j) = 1$ (say all $j$ between $0$ and $q_1$) gives us $p_{n,j} = p_{n, j'}$ by Pigeonhole. In particular, for $n$ large there is a prime $p$ such that $p\mid g(n,j)$ and $p\mid g(n, j')$. On the other hand, $v_p(g(n,j))$ and $v_p(g(n, j'))$ can be arbitrarily large. Since $g(n,j)\mid f(Q^n)-f(j)$, this means that $v_p(f(Q^n)-f(j))$ and $v_p(f(Q^n)-f(j'))$ is arbitrarily large. Thus $v_p(f(j)-f(j'))$ is arbitrarily large, which is an obvious contradiction because $|j-j'|<q_1$. Thus $\frac{f(x)}{x}$ is bounded. Note that $\frac{f(q_i)}{q_i}$ is always an integer. Thus let $R=\max \left(\frac{f(q_i)}{q_i}\right)$ with $V(R) = 1$. We claim that $f(x) = Rx$ for all $x$. First, we will show that $f(Q^n) = R\cdot Q^n$ for $n$ sufficiently large. Note that no prime less than $10^{100}$ can divide $Q^n-q_i$. Thus $V(f(Q^n)-f(q_i)) = V(Q^n-q_i) = Q^n-q_i$. Since $f(q_i) = R\cdot q_i$, we have $f(Q^n) - R\cdot q_i = k(Q^n-q_i)$. Thus $f(Q^n) = k\cdot Q^n + (R-k)\cdot q_i$ where $k$ is a bounded integer. Suppose $R>k$. We claim that for $n$ large enough, $V(k\cdot Q^n+(R-k)\cdot q_i)>1$ when $R\neq k$. First define $-V(x) = V(-x)$. Note that $$k\cdot Q^n+(R-k)\cdot q_i = \frac{R-k}{V(R-k)}\left[\frac{k\cdot Q^n}{\left(\frac{R-k}{V(R-k)}\right)} + q_i\cdot V(R-k)\right] = \frac{R-k}{V(R-k)}\cdot M$$For $n$ sufficiently large, $Q\mid \frac{Q^n}{(R-k)/V(R-k)}$ for all $k$ since $k$ is bounded. Therefore $Q\nmid M$. This means that $V(M) = M>1$, and thus $V(f(Q^n)) > 1$, contradiction! Hence for $n$ large enough, $f(Q^n) = R\cdot Q^n$. Finally, we will show that $f(x) = Rx$ for all $x$. Take $x = V(x)\cdot x'$. For $n$ large, $V(Q^n-x) = V(Q^n - V(x)\cdot x') = V\left(\frac{Q^n}{x'} - V(x)\right) = \frac{Q^n}{x'} - V(x) = V(f(Q^n) - f(x))$. Thus $$f(Q^n)-f(x) = R\cdot Q^n - f(x) = k\left(\frac{Q^n}{x'}-V(x)\right)$$Taking mod $\frac{Q^n}{x'}$ gives us $f(x)\equiv k\cdot V(x)$. By taking $n$ large and noting that $k$ is bounded, we have $f(x) = k\cdot V(x)$. Subbing in for $f(x)$, we get $R\cdot Q^n = k\cdot Q^n/x'$. Thus $k = Rx'$, so $f(x) = Rx'V(x) = Rx$, as desired. Since we WLOGed that $f(0) = 0$, it follows all solutions are of form $\boxed{f(x) = Rx+c}$ with $R$ an integer and $V(R) = 1$. $\square$

This question shows that the hypothesis can be significantly weakened (to $f$ is a bijection modulo $\mathbb{Z}/p\mathbb{Z}$ for every prime $p > 10^{100}$). (The above solutions show that the hypothesis of the original problem is equivalent to $f$ being a bijection modulo $\mathbb{Z}/p^e\mathbb{Z}$ for all such $p$ and any $e$, which is stronger.)

Finally solved this really beautiful and difficult problem. The answer is $f(x) = ax+b$ where $a,b$ are integers such that $a>0$ and $\mho(a) = 0$. It's obvious that this solution works. The main point is to show that these are all solutions. WLOG $f(0)=0$ by shifting. First we setting up some notation. Let $M=10^{100}$. Call a positive integer tasty if and only if all of its prime factors are larger than $M$. Let $T(n)$ denote the largest tasty divisor of $n$. We divide the solution into three parts. Part A: Strengthening the condition Claim: For any tasty integer $t$, $t$ divides $f(a)-f(b)$ if and only if $t$ divides $a-b$. In particular, $T(f(a)-f(b)) = T(a-b)$. Proof: We induct on the size of $t$ with the trivial base case $t=1$. Suppose that the claim is true for any tasty number $t' < t$. Consider $t$ consecutive integers $$f(a+1), f(a+2),\hdots f(a+t).$$If two of them, say $f(r)$ and $f(r+d)$ have the same residue modulo $t$, then $f(r+d)-f(r)$ divides $\mathrm{lcm}(t, T(d))$ by induction hypothesis. Therefore by the functional equation, $$\mho(d) \geq \mho(f(r+d)-f(r)) \geq \mho(\mathrm{lcm}(t,T(d)) \geq \mho(T(d)) = \mho(d)$$Hence all inequalities must be equality. Since $\mathrm{lcm}(t,T(d))$ and $T(d)$ are both large, we get $t\mid T(d)$ which contradicts the induction hypothesis. After a long discussion, we get that $$f(a+1), f(a+2),\hdots f(a+t)$$is complete residue system modulo $t$. Similarly, we get $f(a), f(a+1), \hdots, f(a+t-1)$ is complete residue system modulo $t$. Hence by taking difference, $t\mid f(a+t)-f(t)$. This is enough to conclude the induction. Part B: Proving that $f$ is bounded by linear function (in $\mathbb{Z}^+$) This is the hardest part (but somehow shortest). Fix a positive integer $n>M^{2020}$. Let $K = \mathrm{lcm}_{1\leq i < j \leq M} (f(j)-f(i))$. For each prime $p<M$, we call the index $\in\{1,2,\hdots,M\}$ $p$-murine if and only if $\nu_p(f(n)-f(i)) > \nu_p(K)$. Claim: For each prime $p<M$, there exists at most one $p$-murine index. Proof: Indeed, if $i,j$ are both $p$-murine, then $p^{\nu_p(K)+1}\mid f(i)-f(j)$ which gives contradiction. $\blacksquare$ By the claim, there exists an index $k$ which is not $p$-murine for any prime $p<M$. Now we are happy since $$f(n) - f(k) = T(n-k)\cdot \prod_{p<M} p^{\nu_p(K)} < Kn.$$so $f(n) < Kn+f(M)$. Part C: Conclusion By Part B, let $f(n) < Kn$ for all positive integer $n$. Take a prime $q > K^{2020}$. First, we show a weaker result. Claim: There exists constant $c$ such that $\mho(c)=0$ and $f(n)=cn$ for any tasty $n\equiv 1\pmod q$. Proof: By Dirichlet, take a prime $p\equiv 1\pmod q$ and let $f(p)=cp$ for $c<K$. Suppose that $f(n) = c'n$ where $c'\ne c$. Then we have $$q \mid n-p \text{ and } q\mid f(n)-f(p) = c'n - cp$$thus $q\mid (c-c')p$ which is contradiction since $p>q>c$. $\blacksquare$ Now we take any other prime $r>\max\{M,n\}$. By CRT and Dirichlet, there exist a prime $p$ such that $p\equiv 1\pmod q$ and $p\equiv n\pmod r$. Then note that $$r\mid n-p \implies r\mid f(n)-cp \implies r\mid f(n)-cn$$since this works for any $n$ and any sufficiently large prime $r$, we get $f(n)=cn$ as desired.

CantonMathGuy wrote: This question shows that the hypothesis can be significantly weakened (to $f$ is a bijection modulo $\mathbb{Z}/p\mathbb{Z}$ for every prime $p > 10^{100}$). (The above solutions show that the hypothesis of the original problem is equivalent to $f$ being a bijection modulo $\mathbb{Z}/p^e\mathbb{Z}$ for all such $p$ and any $e$, which is stronger.) Can you provide me an article which proves the S unit equation has only finitely many solutions?

CantonMathGuy wrote: For every positive integer $n$ with prime factorization $n = \prod_{i = 1}^{k} p_i^{\alpha_i}$, define \[\mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.\]That is, $\mho(n)$ is the number of prime factors of $n$ greater than $10^{100}$, counted with multiplicity. Find all strictly increasing functions $f: \mathbb{Z} \to \mathbb{Z}$ such that \[\mho(f(a) - f(b)) \le \mho(a - b) \quad \text{for all integers } a \text{ and } b \text{ with } a > b.\] Proposed by Rodrigo Sanches Angelo, Brazil Excellent problem! Solved with small help from MathLuis. Solution Set The solution set to this functional inequality is \[f(n)=kn+c\]where \(k\) is a positive integer such that \(\mho(k)=0\) and \(c\) is an integral constant. Note. Since \(f\) is a solution implies that \(f+c\) is a solution too, we shall assume that \(f(0)=0\). Notations For brevity, let \(C\) denote \(10^{100}\). We also say that a positive integer \(s\) is superfluous if all it's prime divisors are strictly larger than \(C\). Finally, let \(S(n)\) denote the largest superfluous divisor of \(n\) (if there exists one). Solution The problem is solved in three key claims. Claim 1. \(S(a-b)=S(f(a)-f(b))\). Proof. Let \(S(a-b)=s\). We need to show that \(s\mid f(x+s)-f(x)\) for all integers \(x\). We begin by proving that the set \[\{f(x+1),f(x+2),\hdots,f(x+s)\}\]forms a complete residue system modulo \(s\). Assume not. Then there exists \(1\leq i<j\leq s\) so that \(f(x+i)\) and \(f(x+j)\) leave the same remainder upon division by \(s\). Then, as \[\mho(f(x+j)-f(x+i))\leq\mho(j-i)\]we have \(s\mid j-i\), a contradiction. Therefore, the desired set forms a complete residue system. Analogously, the set \[\{f(x),f(x+1),\hdots,f(x+s-1)\}\]forms a residue system too, implying that \(s\mid f(x+s)-f(x)\) as desired. $\blacksquare$ Note. Define \(\omega_{C}(n)\) to be the product of all prime divisors of \(n\) which are strictly greater than \(C\). Then we have \(\omega_{C}(f(a))=\omega_{C}(a)\). Claim 2. \(f\) is bounded above by a linear function in \(\mathbb{N}\). Proof. Let \(\Omega=\prod_{1\leq j<i\leq C}(f(i)-f(j))\) and let \(n>C\) be a positive integer. Then note that the number of integers \(1\leq k\leq C\) such that \(p^{\nu_p(\Omega)+1}\mid f(n)-f(k)\) for each prime \(p\) is at most one, because if there were two, then \(p^{\nu_p(\Omega)+1}\) would divide \(f(i)-f(j)\), contradicting the definition of \(\Omega\). And since \(\pi(\Omega)<\Omega\), there exists a positive integer \(1\leq m\leq C\) so that \(f(n)-f(m)\) is not divisible by \(p^{\nu_p(\Omega)+1}\) for all primes \(p<C\). Also, let \(f(a)-f(b)=S(a-b)(x_{a,b})\). Then from what we got above, \[x_{n,m}\leq\prod_{p<C}p^{\nu_p(\Omega)}<\Omega\]and also \(S(n-m)<n\), implying that \(f(n)<\Omega n+f(m)\leq n+f(C)\). Therefore, we see that for all \(n>C\), \(f\) is bounded above by a linear function. Also since \(f\) is strictly increasing, there exists a finitely large constant \(\mu\) for which \(f(n)<\mu n\) for all \(n\in\mathbb{N}\), as claimed. $\blacksquare$ Claim 3. \(f(n)=kn\) for all positive integers \(n\). Proof. From the note of claim 1, if \(a\) is a square-free superfluous number, then \(a\mid f(a)\). Now, let \(S\) be the set of all superfluous primes \(p\) congruent to \(1\) modulo another prime \(q>\mu\). Then, from claim 2, there exists a positive integer \(k<\mu\) so that \(f(p)=kp\) for infinitely many primes \(p\) in \(S\). Call this infinite set \(T\). Assume that for some \(\alpha\in S\), \(f(\alpha)=k_0\alpha\) where \(k_0\neq k\). Then, we see that \[q\mid (k-k_0)p\]giving us a contradiction, implying that all primes \(p\equiv1\pmod{q}\) are in \(T\). Therefore, by CRT, there exists a prime \(p\in S\) such that \(p\equiv n\pmod{r}\) where \(r\) is another superfluous prime. From this, we see that \[r\mid p-n\implies~r\mid f(p)-f(n)\implies~r\mid f(n)-kn\]implying that \(f(n)=kn\) for all positive integers \(n\) as desired. $\blacksquare$ Plugging this back into the original inequality, we see that \(\mho(k)=0\), yielding us the solutions presented above, solving the problem.

I would like to thank CANBANKAN for nudging us into the first claim!

CantonMathGuy wrote: For every positive integer $n$ with prime factorization $n = \prod_{i = 1}^{k} p_i^{\alpha_i}$, define \[\mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.\]That is, $\mho(n)$ is the number of prime factors of $n$ greater than $10^{100}$, counted with multiplicity. Find all strictly increasing functions $f: \mathbb{Z} \to \mathbb{Z}$ such that \[\mho(f(a) - f(b)) \le \mho(a - b) \quad \text{for all integers } a \text{ and } b \text{ with } a > b.\] Proposed by Rodrigo Sanches Angelo, Brazil Solution by CANBANKAN which he solved two years ago Let $C=10^{100}$. We split this into three parts: Part 1: Let $L(i)=\prod_{i: ; p_i > C} p_i^{e_i}$. Claim: $L(a-b)=L(f(a)-f(b))$ Proof We proceed by induction. Call a number large if all of its prime divisors are greater than C. The smallest large number greater than C must be prime, call $p0$. For any $n$, consider $f(i){i=n}^{n+p_0}$. By pigeonhole principle, two are congruent modulo $p_0$. If they are not $(n,n+p_0)$, then their difference is less than $p0$, contradicting the condition in the problem. We proceed by strong induction. Assume all large numbers less than $x$, which is also a large number, satisfy the above property. Consider $f(i){i=n}^{n+x}$. By pigeonhole principle, two are congruent modulo $x$. If they are not $(n,n+x)$, then their difference, $d$ is less than $x$. By Inductive Hypothesis, $L(d)=d$, but $x>d$, contradiction. The second step is the key to solving this problem (now having bounded big primes we bound small primes): I claim there exist a constant $c$ such that $f(x)\le cx$ for all $x$. For a prime $p<C$, let $X(p)=max_{j<i<C} \nu_p(f(i)-f(j))$. If there exist $2$ indices, $i,j$ such that $\nu_p(f(n)-f(i)), \nu_p(f(n)-f(j))>X(p)$ then $\nu_p(f(i)-f(j))>X(p)$ contradiction. Hence we can see there $f(n)-f(j)\le L(n-j)\cdot \prod{p<M} p^{X(p)}$ for all \(p<C\). To finish, we can see that $f(p)=c_p\cdot p$ for all large primes $p$. Let $c$ st $f(x)\le cx$. Suppose the difference of two primes much greater than $c$, and contain another big prime factor. We then quickly see that $c_p=c_q$. We can fill big primes this way. For numbers much smaller, by dirichlet, we're done.

We claim that the functions that satisfy are $f(n)=nx+y$ where $x>0$ and $V(x)=0.$ Clearly this works. WLOG $f(0)=0.$ Call any integer huge if it's prime divisors are larger than $10^{100}.$ Let $L(x)$ be the largest huge divisor of $x.$ Lemma 1: $L(u-v)=L(f(u)-f(v))$ for all $u>v.$ Proof. We show, by induction, that any huge $x\mid u-v$ iff $x\mid f(u)-f(v),$ this is essentially the claim. Since it's true for $x=1,$ assume it's true for all $x_0<x.$ Notice that in the sequence $f(u+1), f(u+2), \dots ,f(u+x)$ if $f(v)\equiv f(v+y)\pmod{x}$ then $f(v+y)-f(v)\mid lcm(L(y),x).$ Therefore $V(y)=V(L(y))=V(lcm (L(y),x))=V(f(v+y)-f(v)).$ This implies $x\mid f(y),$ absurd. Thus our sequence is a complete residue system mod $x.$ Our initial claim easily follows. $\blacksquare$ Lemma 2: $\forall n$ we have $f(n)\leq nx.$ Proof. Let $x=100^{100^{100}}.$ And let $X=lcm(f(u)-f(v))$ with not huge non negative $u>v.$ If for any small prime we have $\nu_p(X)< \nu_p(f(x)-f(u))$ and $\nu_p(X)< \nu_p(f(x)-f(v)).$ Then $\nu_p (f(u)-f(v))> \nu_p(X),$ absurd. So this is true for only one, say $u.$ It follows that $f(x)- f(v)=\prod p \cdot L(x-v)< xX.$ This finishes the lemma. $\blacksquare$ Lemma 3: $f(n)=nx$ for all $n.$ Proof. For any prime $p> 10^{100^{100}}$ we have $f(q)=cq$ for any prime $q\equiv 1\pmod p$ with $c$ not huge. Assume that $f(x)=dx$ with $c\neq d.$ Then we force $p\mid cp-dp,$ absurd. By Chinese Remainder Theorem, exists $x\equiv 1\pmod {10^{100^{100}}}$ and $y\equiv x\pmod z.$ Then $f(y)\equiv f(x)=cx\equiv cy\pmod{z}.$ The claim follows and we are done with the problem by shifting back. $\blacksquare$

What an adventure! Let $s(n) = \prod_{p_i < 10^{100}} p_i^{\alpha_i}$. By inducting up over all numbers such that $s(n) = 1$, it is easy to see that any $n$ consecutive numbers always form a complete residue set, hence it follows that the condition is equivalent to the strong condition that $v_p(f(a)-f(b)) = v_p(a-b)$ for all $p > 10^{100}$. WLOG $f(0) = 0$. Now, since there is a finite number of solutions $x, y$ such that $s(x) = 1, s(y) = 1$ and $x-y = 1$ by Kobayashi's theorem, it follows that $\frac{f(n)}{n}$ when $f(n) = 1$ is bounded above by the maximum value of $y$ when $n$ is of the form $\left(\prod_{p_i < 10^{100}} p_i\right)^k+1$, since in those cases it must be that $s\left(\frac{f(n}{n}\right) = \frac{f(n)}{n}$ from the condition on $0, n$ and $1, n$ to obtain the desired result since $s(n)=1, s(n-1) = n-1$. Now consider the set $S$ of numbers congruent to $-1 \pmod {\prod_{p_i < 10^{100}} p_i}$. It follows from the previous result that $\frac{f(n)}{n}$ is bounded above for arbitrary $n$ since all elements of $S$ satisfy the previous result and $S$ is exponentially spaced. We loosen the strong condition to be $v_p(f(a)-f(b)) \geq v_p(a-b)$, then it follows that the set of solutions forms a $\mathbb{Z}-module$, so we can mod out ${x \choose 0}, {x \choose 1}, {x \choose 2}$ so that $f(0) = f(1) = f(2) = 0$ while losing the increasing condition but bounding below by a quadratic. Then it follows that for all $s \in S$, $\frac{s(s-1)(s-2)}{6} \mid f(s)$, so since $f(s)$ is bounded linearly and since $S$ is evenly spaced, it follows that $f(s) = 0$ for all large $s$. Thus returning to the original $f$, it follows that $f$ is quadratic over large $S$. By Schur's theorem, we reach contradiction if $\frac{f(x)}{x}$ is nonconstant, so it follows that $f$ is linear over large $S$. Now, inducting down on the residues modulo $\prod_{p_i < 10^{100}} p_i$, it follows by Dirichlet's theorem that $f(n)$ is linear over all sufficiently large $n$. Hence by Dirichlet's theorem again, it follows that $f(n)$ is linear over all integers, so it is clear that $f(n) = cn$ for $c > 0$ such that $s(c) = c$ is the solution set. Now undoing the $f(0) = 0$ condition, the answer is $f(n) = cn+d$ for $c \in \mathbb{N}$ such that $s(c) = c$, and $d \in \mathbb{Z}$.

Solved with starchan. First, we actually claim that $v_p(f(a) - f(b)) = v_p(a-b)$ for all primes $p > 10^{100}$ and distinct integers $a$ and $b$. The proof is by induction. Let $S$ be the set of all prime powers of big primes and enumerate them in ascending order as $s_1, s_2, \cdots$. Induct to claim that $s \mid f(a) - f(b) \iff s \mid a-b$ for any $s \in S$. Suppose we're at $s_m = p^k$ now. If $k = 1$, then consider $f(1), f(2), \cdots, f(p)$, they must all be distinct modulo $p$ since $i - j$ for $i,j \in \{1,2,\cdots,p\}$ has only prime power divisors smaller than $p$ by induction and for those, the $v_q$ matches exactly. Similarly $f(0), f(2), \cdots, f(p-1)$ is a complete residue class. So $p \mid f(p) - f(0)$, and in general $p \mid f(a) - f(b) \iff p \mid a-b$. If $k \geqslant 2$, using also the fact that the statement is true for $p, p^2, \cdots, p^{k-1}$, a similar argument works. Now, shift $f$ to assume $f(0) = 0$, so $v_p(f(n)) = v_p(n)$ for all big primes $p$, taking $a = n$ and $b = 0$. Next, we claim that if $f(n) < Cn$ for some positive constant $C$, then we are done. Pick a sufficiently large prime $p$ and pick a prime $q \equiv 1 \bmod p$ by Dirichlet (or just cyclotomic polynomials). Since $f(q)$ has big part only $q$, it must equal $f(q) = kq$ for some $k$ with only small prime divisors. Now pick some integer $n \equiv 1 \bmod p$. Then $p \mid n-q$ and so $p \mid f(n) - f(q)$. Now, if $n$ has all big prime factors, then $f(n) = \ell n$ for some integer $\ell$. So $p \mid \ell n - kq \equiv q(\ell - k) \implies p \mid \ell - k$. But since $\ell$ and $k$ are bounded above by $C$, picking $p > \max(C,10^{100})$ causes a contradiction unless $\ell = k$. So we actually get that for any number $n \equiv 1 \bmod p$ with all big prime divisors, $f(n) = kn$. To extend this to all numbers, fix a number $n$, and pick a big prime $q$. We would like to find a $b$ such that $q \mid n-b$ and so $q \mid f(n) - f(b)$. So we want $b$ to be a big number congruent to $1 \bmod p$ and itself have big factors. But we can just pick $b$ to be a prime, by Dirichlet, requiring $b \equiv n \bmod q$ and $b \equiv 1 \bmod p$. Then we get that $q \mid f(n) - f(b) = f(n) - kb \equiv f(n) - kn$. Since $q$ can be made arbitrarily large, this means that $f(n) = kn$ for all $n$. So it suffices to show the existence of such a $C$. Let $M = \pi(10^{100}) + 1$ and let $Z = \prod_{i > j} (f(i) - f(j))$ for $i,j < M$. Since $f$ is strictly increasing, note that this is positive. I claim now that $f(n) < Zn + \max(f(1), f(2), \cdots, f(M))$ for all $n$. To prove this, assume not, then $f(n) - f(i) > Zn$ for all $i = 1,2,\cdots,M$. Therefore, for each $i$, there must be a small prime, say $p_i$ such that $v_{p_i}(f(n) - f(i)) > v_p(Z)$. But since $M$ is more than the number of small primes, this forces that by PHP, some two indices exist such that $p_i = p_j = p$, say. But then $v_p(Z) \geqslant v_p(f(i) - f(j)) = v_p(f(n) - f(i) - (f(n) - f(j))) \geqslant \min(v_p(f(n) - f(i)), v_p(f(n) - f(j))) > v_p(Z)$, a contradiction. Therefore, we do get the existence of such a $C$, and by the middle part of the solution, we obtain that $f(n) = kn$ for some $n$ with $k$ having all small prime factors. Since we had shifted earlier, we can shift back to get the solution set to be $f(n) = kn + \ell$ for some integer $\ell$ and integer $k$ such that all prime factors of $k$ are smaller than $10^{100}$, and these functions clearly work, so we're done. $\blacksquare$

Beautiful problem! This is a very good equality problem that features classic functional NT ideas as well. Smooth $f$ so that $f(0)=0$. We claim that $f(n)=kn$ for any natural $k$ such that $\mho(k)=0$ is the solution set. Let $\varepsilon(n)$ denote the largest divisor of $n$ such that all of its prime divisors are at least $10^{100}$. Lemma: For any $(a, b)$ with $a > b$, \[ \varepsilon(f(a)-f(b))=\varepsilon(a-b). \]Proof. Look at the set $S_a = \{f(a+1), f(a+2), \dots, f(a+k)\}$ of consecutive terms. We will show that for any positive integer $k$ with all prime divisors at least $10^{100}$, $k \mid a - b$ iff $k \mid f(a) - f(b)$, which is sufficient. I contend that $S_a$ is a complete residue system modulo $k$. Assume not. Then there exists two elements $f(a+r)$, $f(a+s)$ of $S_a$ such that $r>s$ and they are congruent modulo $k$. Note that \[ \mho(f(a+r)-f(a+s)) \le \mho(r-s) \]by the problem condition, but this implies that $k \mid r-s$, which is impossible. Thus $S_a$ is a complete residue system modulo $k$. Now shift $S_a$ by one element to $S_{a+1}$, and since both sets are complete residue systems modulo $k$ we have \[ k \mid f(a+k+1)-f(a+1), \]and we conclude. Claim: $f$ has an upper bound given by a linear function over the naturals. Proof. Let \[ M = \operatorname{lcm}_{(i, j) \in [1, 10^{100}]^2, i>j} \: [f(i)-f(j)]. \]Note that by the prior lemma, \[ \frac{f(a)-f(b)}{\varepsilon(a-b)} = \frac{f(a)-f(b)}{\varepsilon(f(a)-f(b))} < M, \]and since $\varepsilon(a-b) \le a-b$, we have \[ f(a)-f(b) \le (a-b)M. \]Thus $f(n) \le M \cdot n$ for all $n \in \mathbb{N}$, as required. Claim: For some fixed $k$ with $\mho(k)=0$, $f(n)=kn$ for all natural $n$. Proof. Call a prime huge if it is at least $10^{100}$. Fix a huge prime $p$. Then for any prime $q \equiv 1\pmod{p}$, we have $f(q)=kq$ for some constant $k$ by the second claim. Suppose that for some huge prime $x \equiv 1 \pmod{p}$, $f(x)=k'x$ for some $k' \neq k$. Then $p \mid (k-k')q$ for all $q \equiv 1\pmod{p}$, a contradiction. For each $n \in \mathbb{N}$, there exists a huge prime $p$ such that $p-n$ has a huge prime divisor $t$. But then $t \mid p-n$ implies $t \mid f(n)-kn$, so $f(n)=kn$. Now $\mho(k(a-b)) \le \mho(a-b)$ whenever $a>b$, but this means that $\mho(k)=0$, as desired. It is easy to check that all $k$ with $\mho(k)=0$ produce valid solutions, and we conclude. Edit: the above solution shows the desired results for naturals, but it works out in general since letting $n$ be any integer instead of a natural number does not break any logic. In particular, the solution extends very easily to integers.

We claim the only solutions are of the form $f(a)=kx+c$ where $\Omega(k)=0$. It suffices to show the following claim: Quote: Let $f:\mathbb{Z} \rightarrow \mathbb{Z}$ be a strictly increasing function such that $f(0)=0$ and \[\Omega(f(a)-f(b))\le \Omega(a-b)\]for all $a>b$. Then, there exists $k\in \mathbb{Z}_{>0}$ with $\mho(k)=0$ such that $f(x)\equiv kx$. Let $\alpha$ be the product of every prime under $10^{100}$. For a positive integer $n$ with prime factorization $n = \prod_{i = 1}^{k} p_i^{\alpha_i}$, let \[\omega(n) = \prod_{i: \; p_i > 10^{100}} p_i^{\alpha_i}.\] Claim: Let $n=p^r$ for some prime $p>10^{100}$. Then, for all $x$, $f(x), f(x+1), \dots, f(x+n-1)$ covers every residue class mod $n$ once, which implies that $f(x) \pmod{n}$ only depends on $x \pmod{n}$. Proof: It suffices to show this claim for $x=0$. We will prove this by induction on $n$. Assume toward a contradiction that for some $0\le a, b < n$, $f(a) \equiv f(b) \pmod{n}$. Let $\omega(f(a)-f(b)) = p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}$ where $p_1,\dots, p_m$ are distinct primes. Then, \[p_1^{a_1}, p_2^{a_2}, \dots, p_m^{a_m} < n.\]So, by induction, $f(a) \equiv f(b) \pmod{p_i^{a_i}}$ for all $1\le i\le m$. Therefore, $\text{lcm}(n, p_1^{a_1}p_2^{a_2}\dots p_m^{a_m})\mid f(a) - f(b)$. So, \[\mho(f(a) - f(b)) \ge \mho(\text{lcm}(n, p_1^{a_1}p_2^{a_2}\dots p_m^{a_m})) > \mho(p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}) = \mho(a-b),\]a contradiction. Claim: There exists a constant $C$ such that for sufficiently high $x$, \[f(x) \le Cx.\] Proof: Let $p_1, p_2, \dots, p_m$ be the primes under $10^{100}$. Let $x_i$ be the maximum value of $\nu_{p_i}(f(a)-f(b))$ for $0\le b<a\le m$. Let $M$ be the maximum value of $f(a)$ for $0\le a \le m$. Let $n>M$ be a positive integer. Assume toward a contradiction that $\nu_{p_i}(f(n)-f(a)), \nu_{p_i}(f(n)-f(b)) > x_i$ for $0\le b<a\le m$. Then, $p^{x_i+1}\mid f(a)-f(b)$, a contradiction. So, $\nu_{p_i}(f(n)-f(a))> x_i$ for at most one value $0\le a \le m$. So, for some $0\le a \le m$, $\nu_{p_i}(f(n)-f(a)) \le x_i$ for all $i$. So, \[f(n)-f(a) \le p_1^{x_1}\dots p_m^{x_m} \omega(n-a) \le p_1^{x_1}\dots p_m^{x_m}n\]\[f(n) \le p_1^{x_1}\dots p_m^{x_m}n + M \le (p_1^{x_1}\dots p_m^{x_m}+1)n.\] Claim: There exists $k \in \mathbb{Z}_{>0}$ such that for sufficiently high $x$, \[f(\alpha x + 1) = k(\alpha x + 1).\] Proof: We have previously shown $\omega(f(\alpha x + 1)) = \omega(\alpha x + 1)$. Therefore, $f(\alpha x + 1)$ is an integer multiple of $\alpha x + 1$. Let $f(\alpha x + 1) = g(x)(\alpha x + 1)$. Then, $g(x)$ is bounded. Let $k$ be the highest positive integer such that $g(x)=k$ for arbitrarily high $x$. For sufficiently high $x$, $(k-1)(\alpha (x+1)+1) < k(\alpha x + 1)$. So, after that point, $g(x)$ cannot go from being at least $k$ to being below $k$. So, for sufficiently high $x$, $g(x) = k$. Claim: For all $x$, \[f(x) = kx.\] Proof: Let $x$ be a positive integer. Then, for sufficiently high $y$, \[\omega(\alpha y + 1 - x) = \omega(f(\alpha y + 1) - f(x))\]\[\omega(\alpha y + 1 - x) \mid k(\alpha y + 1) - f(x)\]\[\omega(\alpha y + 1 - x) \mid kx - f(x).\]Because $\omega(\alpha y + 1 - x)$ can be arbitrarily high, $f(x)=kx$.