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$.