Pretty fun problem! The key claim is the following. Claim: There exists some integer $r$ satisfying $$r \equiv x\pmod {f(x)}$$for all $x$. Proof. We'll construct $r$ with CRT by computing the correct residue for $r$ modulo each prime power. For every prime $p$ dividing some $f(x)$, choose $x_p$ such that $\nu_p(f(x_p))$ is maximal. Then there is some $r$ satisfying $$r\equiv x_p\pmod {p^{\nu_p(f(x_p))}}$$for all $p$. We want to show that $r\equiv y\pmod {f(y)}$ for all $y$, so it suffices to show that $r\equiv y\pmod {p^k}$ for any prime power $p^k\mid f(y)$. Indeed, since $p^k\mid f(x_p)$ and $f(y)$, we know that \begin{align*} \gcd(f(x_p), f(y)) = \gcd(f(x_p), x_p-y) &\implies p^k\mid x_p-y \\ &\implies r\equiv x_p\equiv y\pmod {p^k}, \end{align*}which proves the claim. $\blacksquare$ Now for any $x$, we have $$\gcd(f(x), f(r)) = \gcd(f(x), x-r) = f(x) \implies f(x)\mid f(r).$$But then $$f(x) = \gcd(f(x), f(r)) = \gcd(f(r), r-x).$$Thus, taking $n = f(r)$ and $m = k\cdot f(r) - r$ for sufficiently large $k$ gives positive $m$ and $n$ such that $f(x) = \gcd(m+x, n)$.

Simple follow-up (and probably the question I should have asked instead): how many such functions are there?

Let $p\le 10^{100}$ be a prime. Set $x$ such that $\nu_p\big(f(x)\big)$ is maximal, so that for all $y$, $$\nu_p\big(f(y)\big)=\min\big[\nu_p\big(f(x)\big),\,\nu_p(x-y)\big].$$It is immediate that all $y$ of the form $x+kp^{\nu_p(f(x))}$ have maximal $\nu_p\big(f(y)\big)$, so $\nu_p\big(f(y)\big)$ is maximal when $$y\equiv x\pmod{p^{\nu_p(f(x))}}.\qquad(*)$$By the Chinese Remainder Theorem, there exists negative $z$ obeying $(*)$, so taking $m=-z$ and $n=f(z)$ yields $f(y)=\gcd(n,\,y+m)$, as desired. $\square$

Let $P(x, y)$ denote the assertion, as usual. Note that if $f$ is such a function, then $g(x) \equiv f(x + c)$ works, too, so WLOG assume $f$ achieves its maximum at $f(0)=C$. Considering $P(0,x)$ gives \[\gcd(C, f(x)) = \gcd(C, x) \quad (\heartsuit)\]so in particular if $C \mid x$ then $C \mid f(x)$ which implies $f(x) = C$ by maximality. Now let $x$ be arbitrary and let $d = \gcd(C, x)$. Note that $d \mid f(x)$, so write $f(x) = kd$ for some $k \in \mathbb{N}$ with $\gcd(k, C/d) = 1$ by $(\heartsuit)$. I claim $k=1$. Pick some $y'$ satisfying \begin{align*} y' &\equiv 0 \pmod{C/d} \\ y' &\equiv x/d \pmod{k} \\ \end{align*}and let $y = y'd$ so that $C \mid y$ and $f(x) \mid y-x$. By an earlier observation, we must have $f(y) =C$, but taking $P(x, y)$ gives \[\gcd(f(x), f(y)) = \gcd(f(x), x-y) = f(x)\]implying $f(x) \mid f(y) = C$ and thus $k \mid C/d$. As $\gcd(k, C/d)=1$, we must have $k=1$, as desired. It follows that $f(x) = \gcd(C, x)$ for all $x$, and accounting for the shift we are done.

Official solution: Let $\mathcal{P}$ be the set of primes not exceeding $10^{100}$. For each $p \in \mathcal{P}$, let $e_p = \max_x \nu_p(f(x))$ and let $c_p \in \operatorname{argmax}_x \nu_p(f(x))$. We show that this is good enough to compute all values of $x$, by looking at the exponent at each individual prime. Claim: For any $p \in \mathcal P$, we have $\nu_p(f(x)) = \min(\nu_p(x - c_p), e_p)$. Proof. Note that for any $x$, we have $ \gcd(f(c_p), f(x)) = \gcd(f(c_p), x - c_p)$. We then take $\nu_p$ of both sides and recall $\nu_p(f(x)) \le \nu_p(f(c_p)) = e_p$; this implies the result. $\blacksquare$ This essentially determines $f$, and so now we just follow through. Choose $n$ and $m$ such that \begin{align*} n &= \prod_{p \in \mathcal P} p^{e_p} \\ m &\equiv -c_p \pmod{p^{e_p}} \quad \forall p \in \mathcal P \end{align*}the latter being possible by Chinese remainder theorem. Then, from the claim we have \begin{align*} f(x) &= \prod_{p \in \mathcal P} p^{\nu_p(f(x))} = \prod_{p \mid n} p^{\min(\nu_p(x-c_p), e_p)} \\ &= \prod_{p \mid n} p^{\min(\nu_p(x+m), \nu_p(n))} = \gcd\left( x+m, n \right) \end{align*}for every $x \in {\mathbb Z}$, as desired. Remark: The functions $f(x) = x$ and $f(x) = |2x - 1|$ are examples satisfying the gcd equation (the latter always being strictly positive). Hence the hypothesis $f$ bounded cannot be dropped. Remark: The pair $(m, n)$ is essentially unique: every other pair is obtained by shifting $m$ by a multiple of $n$. Hence there is not really any choice in choosing $m$ and $n$.

I am probably making some mistake but i cant find it so please help. I get that for any $m,n$ the function $f(x) = \gcd(m+x, n)$ works. We will show $$\gcd ( \gcd (m+x, n), \gcd (m+y, n))= \gcd ( \gcd(m+x, n),x-y)$$Let $$m+x=ka$$$$n=kb$$$$m+y=lc$$$$n=ld$$with $\gcd (a,b)=1$ and $\gcd (c,d)=1$ Let $\gcd (k,l)=s$ so we need to show $$s=\gcd ( \gcd(m+x, n),x-y)$$or $$s=\gcd ( \gcd(m+x, n),(m+x)-(m+y))=\gcd ( \gcd(m+x, n),m+y)$$(because $\gcd(m+x, n)|m+x$) This is equivalent to $s=\gcd (k,lc)=s(k_1,l_1c)$ or $\gcd (k_1,l_1c)=1$ which is same as $\gcd (k_1,c)=1$ ($\gcd (k_1,l_1)=1$) where $k=k_1s$ and $l=l_1s$ . Now if $r|k_1,c$ then from $$n=k_1sa=l_1sc$$we get $k_1a=l_1c$ and $r|l_1c$ but $$\gcd (r,l_1)=\gcd (k_1,l_1)=1$$so $r|c$ Then because $r|d,c$ we get $r=1$ which is wanted.

FISHMJ25 wrote: I am probably making some mistake but i cant find it so please help. No mistake. Everything you said is correct. Just that you didn't solve the problem. The problem does not ask you to show that a function of this specific form satisfies the functional equation but that every function satisfying the functional equation is already of this specific form.

Tintarn wrote: FISHMJ25 wrote: I am probably making some mistake but i cant find it so please help. No mistake. Everything you said is correct. Just that you didn't solve the problem. The problem does not ask you to show that a function of this specific form satisfies the functional equation but that every function satisfying the functional equation is already of this specific form. I understand that but in other solutions they showed that only specific $m$ and $n$ work which is contradiction with what i wrote.

Well, they showed that for a given function $f$, essentially only a unique value of $m$ and $n$ works. But of course there is more than one such function $f$...

I get it thanks i appreciate it!

Solution with mfang92 Fix $p \le 10^{100}$ and choose $x$ such that $\nu_{p} (f(x))$ is maximal. Then from the condition, $$\min(\nu_p(f(x)), \nu_p(f(y)) = \min(\nu_p(f(x)), \nu_p(x-y)) \implies \nu_p(f(y)) = \min(\nu_p(f(x)), \nu_p(x-y))$$so we have that $\nu_p(f(y)) = \nu_p(f(x))$ (i.e, $\nu_p(f(y))$ is maximized) if $\nu_p(x-y) \ge \nu_p(f(x))$ or $y = kp^{\nu_p(f(x)} + x$. Now, we want $$\nu_p(f(y)) = \min(\nu_p(m+y), \nu_p(n)).$$Taking $n = f(x)$ and $m = -x$, we get $\nu_p(f(y)) = \min(\nu_p(-x+y), f(x))$ as desired. $\blacksquare$

Taking the $\nu_p$ of both sides gives

Then \[ \nu_p(f(y)) = \min(C_p, \nu_p(x_{p,max}-y)) = \min(C_p, \nu_p(y-x_{p,max}). \]What we want is to find integers $m,n$ such that \[ \nu_p(f(y)) = \min(\nu_p(n), \nu_p(m+y)). \]So taking $\nu_p(n) = C_p$ and $m=-x_{p,max}$ works. But we want this single values for $m,n$ regardless of $p$. We can fix this with CRT: the following works: \begin{align*} n &= \prod_{p \le 10^{100}} p^{C_p} \\ m &\equiv -x_{p,max} \pmod{p^{C_p}}. \end{align*}

Nice! Here's my solution (pretty much the same as the above solutions): First of all, it's easy to see that if $f$ is constant, then we must have $f \equiv 1$ (since this constant value divides $x-y$ for all integers $x,y$). In this case, $n=1$ and $m=\text{anything}$ works. So from now on assume $f$ is non-constant. Note that we have $$\gcd(f(x),f(x+af(x)))=\gcd(f(x),x-(x+af(x)))=f(x) \Rightarrow f(x) \mid f(x+af(x)) \text{ } \forall a \in \mathbb{Z}$$The main claim is as follows- CLAIM Let $k$ be an integer such that $f(k)=\max_{x \in \mathbb{Z}} f(x)$. Then $f(x) \mid f(k)$ for all $x \in \mathbb{Z}$. Proof of Claim Since for any $a \in \mathbb{Z}$, we have $f(x) \mid f(x+af(x))$, so it suffices to show that there exists $k \in \mathbb{Z}$ such that $k \equiv x \pmod{f(x)}$ for all $x \in \mathbb{Z}$ (Since in that case $f(x) \mid f(k)$ gives that this $k$ is the same as the one given in the statement of our claim). For some $x \in \mathbb{Z}$, consider a prime $p$ dividing $f(x)$ (at least one such prime $p$ exists since $f$ is non-constant). Let $y \in \mathbb{Z},e \in \mathbb{N}$ be the integers such that $e=\nu_p(f(y))$ is maximum as $y$ varies over $\mathbb{Z}$. Using CRT, choose $k \equiv y \pmod{p^e}$, and do so for all primes $p$ dividing some element in the range of $f$. Now, for any $z \in \mathbb{Z}$, if $p^m \mid f(z)$ with $1 \leq m \leq e$, then $$p^m \mid \gcd(f(y),f(z))=\gcd(f(y),y-z) \Rightarrow p^m \mid y-z \Rightarrow k \equiv y \equiv z \pmod{p^m}$$Thus, we can form such a $k$ using CRT for all primes dividing $f(x)$ as $x$ varies on $\mathbb{Z}$, giving the desired result. $\Box$ Let $k$ be as in our claim. Since $f(k)$ is maximum, and $f(k) \mid f(k+af(k))$, so we get $f(k+af(k))=f(k)$ for all $a \in \mathbb{Z}$. Let $n=f(k)$ and $m=af(k)-k$ with $a$ sufficiently large (so that $m>0$). Then, using our claim, we get $$f(x)=\gcd(n,f(x))=\gcd(f(-m),f(x))=\gcd(f(-m),-m-x)=\gcd(m+x,n) \text{ } \blacksquare$$

The condition translates to for all prime $p$, $\min(\nu_p(f(x)), \nu_p(f(y)))=\min(\nu_p(f(x), \nu_p(x-y))=\min(\nu_p(f(y)), \nu_p(x-y))$ for all $x, y$. Let $P$ be the set of primes which divide some $f(x)$. Let $p$ be a fixed prime in $P$; then, since $f$ is bounded, let $k$ be an integer such that $\nu_p(f(k))=c$ is maximal; so, $\nu_p(f(x))\le c$ for all $x$. Now, set $y=k$, so we have $\min(\nu_p(f(x)), c)=\min(c, \nu_p(x-k))$. From this, we have that if $\nu_p(f(x))<c$, then we have $\nu_p(f(x))=\nu_p(x-k)$. Hence, for all $x$, either $\nu_p(x)=c$, or $\nu_p(x)=\nu_p(x-k)$, meaning $\nu_p(x)=\min(\nu_p(x-k), \nu_p(p^c))$. Combining this for all primes in $P$ and then doing CRT finishes the problem.

It suffices to show that there exist $m,n$ such that for every prime $p$, we have $\nu_p(f(x)) = \text{min}(\nu_p(x+m),\nu_p(n))$. Since the range of $f(x)$ is finite, let the maximum value of $\nu_p(f(x))$ be $M$. Note that if some function $g(x)$ satisfies the given condition, then $g(x+a)$ also does for any integer $a$. Thus let us shift so $\nu_p(f(0))=M$, and take $x=0$ in the initial condition. We get $\nu_p(f(y)) = \text{min}(M,\nu_p(y))$ for every integer $x$, which implies that there exists an integer $n$ with $f(y)= \text{gcd}(y,n)$ for all $y$; shifting back gives the solution set as $f(y)=\text{gcd}(y+m,n)$ as desired.

Remark: What the problem was asking for just felt kind of contrived. Pick some arbitrary prime $p \leq 10^{100}$. The problem translates to\[\min[v_p(f(x)), v_p(f(y))] = \min[v_p(f(x)), v_p(x-y)]\]for all $x, y \in \{1, 2, \ldots , 10^{100}\}$. Suppose we choose $c_p$ such that $v_p(f(c)) = e_p$ is maximal. Then, we see that\[v_p(f(y)) = \min[e_p, v_p(c_p - y)] = \min[e_p, v_p(y-c_p)]\]for all $y \in \{1, 2, \ldots , 10^{100}\}$. Note that since $\gcd$ is multiplicative over primes we can basically put this together to solve the problem. We simply choose \[n = \prod_{1 \leq p \leq 10^{100}}p^{e_p}\]\[m + c_p \equiv 0 \text{ }(\text{mod }{p^{e_p}})\text{ } \forall 1 \leq p \leq 10^{100}\]which is easily shown to work since if we take any $y$ and then multiply\[v_p(f(y)) = \min[e_p, v_p(y-c_p)]\]across all primes $p \mid y$, we get\[f(y) = \prod_{p \mid y} p^{\min[e_p, v_p(y - c_p)]} = \prod_{p \mid y} p^{\min[v_p(n), v_p(y + m)]} = \gcd(n, x + m)\]as desired. $\blacksquare$

jj_ca888 wrote: Remark: What the problem was asking for just felt kind of contrived. I wanted to simply ask contestants to solve the functional equation, but was worried that some students might not realize that the solutions are described by $x \mapsto \gcd(m+x, n)$ (and perhaps give a more complicated description instead). So instead I asked to just show that every solution to the FE is of the correct form. Posing the variant in #4 would've solved this issue, but when I created this problem, for some reason I thought the variant didn't have a nice answer. (I think not giving the answer $x \mapsto \gcd(m+x, n)$ might also make the problem harder.)

Solved with help from pinetree1. First, we note that for all values, then $$\gcd(f(x), x-y) = \gcd(f(x), f(y)) = \gcd(f(y), f(x)) = \gcd(f(y), y-x) = \gcd(f(y), x-y)$$which means that if $x \ne y$ and $f(x)=f(y)$, then for all prime $p$, $\max(v_p(f(x)), v_p(x-y)) = \max(v_p(f(y)), v_p(x-y))$. This means that for all prime $p$, $v_p(f(x)) = v_p(f(y)) \le v_p(x-y)$ or $ v_p(x-y)\le v_p(f(x)), v_p(f(y))$. However, if $x \ne y$ we also observe that $f(x) \mid x-y$. So, for all prime $p$, $v_p(f(x)) \le v_p(x-y)$ if $f(x) = f(y)$. Now, $\gcd(f(x), f(y)) = \gcd(f(x), x-y)$, so if $f(x)$ divided $f(y)$ then $f(x)$ also divides $x-y$. Let's prove there is always a constant $m$ such that if $f(x) \mid f(m)$, then $f(m) \mid x-m$ for all $x$. Note that if we take $\pmod{f(x)}$, then we need to prove for all $1 \le k \le 10^{100}$ that there exists such an $m$ satisfying $m \equiv k \pmod{f(k)}$. Now, observe that for all prime $p$, if we have two $f(x)$ and $f(y)$, such that $v_p(f(x)) \ge i$ and $v_p(f(y)) \ge i$ for some $i$, then $v_p(\gcd(f(x), f(y))) \ge i$ so $v_p(\gcd(f(x), x-y)) \ge i$ and so $p^i \mid x-y$. By the Chinese Remainder Theorem, due to this fact, we have such a solution $m$. As a result, this gets us that we are done.

We can make a table, with columns numbered $\dots -2, -1, 0, 1, 2, \dots$ and rows labelled with each prime in $\{1, 2, \dots, 10^{100}\}$. In each entry on row $p$ and column $i$, we write $v_p f(i)$. For each $i$, the entries in column $i$ uniquely determine $f(i)$ because it just says the prime factorization of $f(i)$. Claim: if the entry in row $p$ and column $i$ is $C$, any entry in row $p$ and a column numbered $j$ is at least $C$ iff $i \equiv j \pmod{p^C}$. Proof: the original FE. If $i \equiv j \pmod{p^C}$, plugging in $x = i$ and $y = j$ gives us that $\gcd (f(i), f(j)) = p^C$; otherwise, the $v_p$ of the GCD is less than $C$. So, each row in the table is just $\dots v_p (-2), v_p (-1), v_p (0), v_p (1), v_p (2), \dots$, except everything greater than some constant $C$ is just replaced with $C$, and the row is shifted in some way. Claim: There exist positive integers $m$ and $n$ such that $f(x) = \gcd(m+x, n)$ for all integers $x$. Proof: Let $M_p$ be the largest value in row $p$ for each $p$. Because of CRT, there is a column $i$ we can pick where the entries in each row are $M_2, M_3, M_5, \dots$. Let $m = -i$, let $n = 2^{M_2} \cdot 3^{M_3} \cdot 5^{M_5} \cdot \dots$. rip awful writeup sorry future me

Fix a prime $p$. Then the condition becomes $\min(\nu_{p}(f(x)), \nu_{p}(f(y))) = \min(\nu_{p}(f(x), x - y)$ for all $x, y \in \mathbb{Z}$. Since the images of $f$ are bounded above, we can take $k$ such that $\nu_{p}(k)$ is maximal. Then for all $s \in \mathbb{Z}$, we have $\min(\nu_{p}(f(k), \nu_{p}f(s))) = \min(\nu_{p}(f(k)), \nu_{p}(k - s))$, so $\nu_{p}(f(s)) = \min(\nu_{p}(f(k)), k - s)$. Since the images of $f$ are bounded above, there are finitely many prime $p$ such that there exists $a$ such that $p$ divides $f(a)$. So we can choose $m$ by using Chinese remainder theorem and letting $n$ be the product of $p^{\nu_{p}(f(k))}$'s, we have $f(x) = \gcd(m + x, n)$. Thus we're done. $\blacksquare$

Note that the condition means that: \[\min\{v_p(f(x)),v_p(f(y))\}=\min\{v_p(f(x)),v_p(x-y)\}.\]As the range of $f$ is on a closed interval, there must exist an absolute max of the function. Also, there must exist an absolute max of $v_p((f(x))$ for all prime $p$ in the range of $f$. Call this max $y_p$ and call the value of $x$ at this max, $x_p$. Claim: $v_p(f(x))=\min\{y_p,v_p(x_p-x)\}$ Proof: Set $y=x$ and $x=x_p$, getting: \[v_p(f(x))=\min\{y_p,v_p(x_p-x)\},\]as desired. Note that $v_p(a)=v_p(b)$ if $b\equiv a\pmod{p}$. Consider a $m$ such that: \[m\equiv -x_p\pmod{p}.\]By CRT, there exists such a $m$ for all $p$ in the range of $f$. We then get: \[v_p(f(x))=\min\{y_p,v_p(m+x)\}.\] Note that $f(x_p)\equiv 0\pmod{p^{y_p}}$ and $f(x_p)\not\equiv 0\pmod{p^{y_p+1}}$. As all $p$ in the range are relatively prime, there exists a $n$ such that: \[n=f(x_p), \forall p\in \{1,\dots,10^100\}=\Pi_{p\in \{1,\dots,10^{100}\}}{p^{y_p}}.\] Therefore, we can say that: \begin{align*} v_p(f(x))&=\min\{v_p(n),v_p(m+x)\}\\ &=v_p(\gcd(n,m+x)),\\ \end{align*}as desired.

Let $p \le 10^{100}$ be a prime number and let $x$ be the maximal value of $\nu_p(f(x))$ so that for all $y$ \[\nu_p\left(f(y)\right)=\min\left[\nu_p\big(f(x)\big),\,\nu_p(x-y)\right].\] Clearly, all $y$ of the form $x+cp^{\nu_p(f(x))}$ have maximal $\nu_p\left(f(y)\right)$, so $\nu_p\left(f(y)\right)$ is maximal when \[y\equiv x\pmod{p^{\nu_p(f(x))}}.\quad(\star)\] There exists a negative value $z$ satisfying $\star$, so $(m,n)=(-z, f(z))$ yields the desired result. $\square$

Fix any prime $p$ less than $10^{100}$. It suffices to show that the desired holds under $\nu_p$ analysis. Let $x$ be an integer such that $\nu_p(f(x))$ is maximal. Then for any $y$ distinct from $x$, \[ \nu_p(f(y)) = \nu_p(x - y). \]Taking $n=f(x)$ and $m \equiv -x \pmod{p^{\nu_p(f(x)}}$, $y \neq x$ satisfy the desired. Realize that plugging in $x$ into the desired with these values of $m$ and $n$ returns a valid equality, as desired.

Suppose $S$ is the set of primes under $10^{100}$, $p$ as an arbitrary prime in $S$, $e_p$ be the maximum possible value $v_p(f(x))$, and $x_p$ be a value of $x$ for which this maximum holds. Using $v_p$ and substituting $(x,y) = (x_p,t)$, we get \[\min \left(v_p(f(x_p)), v_p(f(t))\right) = \min \left(v_p(f(x_p)), v_p(x_p-t)\right)\]\[\implies v_p(f(t)) = \min(e_p, v_p(x_p-t)).\] Then we construct our values of $m$ and $n$ such that \[m = -x_p \pmod{p^{e_p}} \quad \forall \quad p \in S, \qquad n = \prod_{p \in S} p^{e_p},\] which works as \[v_p(\gcd(n, x+m)) = \min(v_p(n), v_p(x+m)) = \min(e_p, v_p(x-x_p)) = v_p(f(x))\] for all primes $p \in S$ and $x \in \mathbb{Z}$. $\blacksquare$

Ew. Weird, intractable number theory because I'm bad. The idea is to interpret the condition in $\nu_p$. We are motivated to do so because in terms of $\nu_p$ the desired conclusion can be restated in terms of individual primes. Then fix a prime $p$. Then over all primes the given can be restated as, \begin{align*} \min(\nu_p(f(x)), \nu_p(f(y))) = \min(\nu_p(f(x)), \nu_p(x-y)) \end{align*}Consider $k_p$ such that $\nu_p(f(k_p))$ is maximal. Also let $\nu_p(f(k_p)) = e_p$. Then we find we have, \begin{align} \nu_p(f(x)) = \min (e_p, \nu_p(x-k_p)) \end{align}Now a hint told me to use CRT because I'm bad. To finish note that we want to find $m$ and $n$ such that we always have, \begin{align*} \nu_p(f(x)) = \min(\nu_p(m+x), \nu_p(n)) \end{align*}over all primes $p$. Now choose $m$ satisfying, \begin{align*} m \equiv -k_p \pmod{p^{e_p}} \end{align*}over all $p$. A solution is guaranteed by CRT. Similarly for $n$ choose it to satisfy, \begin{align*} n \equiv 0 \pmod{p^{e_p}} \end{align*}for all $p$ which exists, once again, by CRT. Now from $(1)$ our choices of $m$ and $n$ suffice.

Take $x_0$ such that $\nu_p(f(x_0))$ is max for some given prime p. Let $x = x_0$, we get $\min(\nu_p(f(x_0)), \nu_p(x_0-y)) = \nu_p(f(y))$. Now take $m \equiv -x_0 \pmod {p^{\nu_p(f(x_0))}}$, $n \equiv f(x_0) \pmod {p^{\nu_p(f(x_0))}}$ $\Rightarrow$ such $f(x)$ satisfies a condition equivalent to the one we wanted. If we use this expression over all valid p, we get a working solution (m, n) by CRT.

If we rephrase the problem in terms of $\nu_p$ we have that for all primes $p$, $$\min(\nu_p(f(x)),\nu_p(f(y))=\min(\nu_p(f(x)), \nu_p(x-y))$$for all integers $x,y$. Now since the image of $f$ is bounded, we know that there exists some $c$ such that $\nu_p(f(c))=s$ is maximized. Note that if we fix $x=c$, then that reduces the above condition to $\nu_p(f(y))=\min(s, \nu_p(c-y))$ for every positive integer $y$, so we are done if we can prove that $\min(s, \nu_p(c-y))=\min(\nu_p(m+y),\nu_p(n))$ for some integer $m,n$. Suppose the set of primes contained in $\{1, 2, \ldots, 10^{100}\}$ is $P=\{p_1, \ldots, p_k\}$. Now note that if we take $n=\prod_{p \in P}p_i^{e_{i}}$ where $e_i$ is the maximal power of $p_i$ contained in $\{1, 2, \ldots, 10^{100}\}$, would have $\nu_p(n)$ be maximized for any prime $p$, thus $\nu_p(n)=s$. Now we just need $\nu_p(m+y)=\nu_p(c-y)$ for all $p$. Note that when $c-y \equiv 0 \mod{p_i^{e_i}}$, we have $y \equiv c \mod{p_i^{e_i}}$. That means we just need \begin{align*} m &\equiv -c \mod{p_1^{e_1}}\\ m &\equiv -c \mod{p_2^{e_2}} \\ &\vdots \\ m &\equiv -c \mod{p_k^{e_k}} \end{align*}By CRT we know such a positive integer $m$ exists. Thus we are done.

Suspiciously simple solution without modular arithmetic

Fun problem! Solution. For each prime $p < 10^{100}$, let $P_p = p^k$ denote the largest power of $p$ for which $P_p \mid f(x)$ for some $x$. The main idea is the following: Claim: Suppose $P \mid P_p$. All integers $x$ for which $P \mid f(x)$ are congruent mod $P$. Proof. Let $x, y$ be integers for which $P \mid f(x), f(y)$, and suppose to the contrary that $\nu_p(x - y) < \nu_p(P) \leq k$. Then \[\min(\nu_p(f(x)), \nu_p(f(y))) \geq k > \nu_p(x - y) = \min(\nu_p(f(x)), \nu_p(x - y))),\]so our assumption was wrong. $\square$ Thus for each $p$, there is a unique integer $a_p \in [0, P_p - 1]$ for which all solutions of $f(x) \equiv 0 \pmod{P_p}$ satisfy $x \equiv a_p \pmod{P_p}$. We now claim that taking $m > 0$ such that $m \equiv -a_p \pmod{P_p}$ for all $p < 10^{100}$ (possible by CRT) and setting $n = \prod_p P_p$ is a valid choice of $(m, n)$. Indeed, let $p$ be a prime, and $x$ an integer with $\nu_p(f(x)) = \ell$. Since $x \equiv a_p \pmod{p^\ell}$ and $x \not\equiv a_p \pmod{p^{\ell + 1}}$, we have \[\nu_p(\gcd(m + x, n)) = \min(\nu_p(m + x), \nu_p(n)) = \min(\nu_p(x - a_p), \nu_p(n)) = \ell = \nu_p(f(x))\]from the fact that $\nu_p(n) = \nu_p(P_p)$. Combined with the observation that $\nu_p(f(x)) = 0 = \nu_p(n)$ for all primes $p > 10^{100}$, this completes the proof. $\square$ Remark. I had to edit the above proof a bit, since originally I assumed taking $n = \text{lcm}(1, 2, \dots, 10^{100})$ was fine. But after looking at hints, I realized this raises issues when some prime power dividing $\text{lcm}(1, 2, \dots, 10^{100})$ isn't actually in the range of $f$.

For a prime $p$ we have $\min(\nu_{p}(f(x)), \nu_{p}(f(y))) = \min(\nu_{p}(f(x), \nu_{p}(x - y))$, let $x$ be the maximal value of $\nu_{p}(f(x))$, so we have $$\nu_{p}(f(k))=\min(\nu_{p}(f(x)),\nu_{p}(k-x))\qquad{(*)}$$We basically want to always have $\nu_p(f(x)) = \min(\nu_p(m+x), \nu_p(n))$. Now choose $m\equiv -x \pmod{p^{\nu_{p}(f(x))}}$ and $n\equiv f(x)\pmod {p^{\nu_{p}(f(x))}}$ by CRT and we are done!

Define $x_p$ to be the maximal value such that $\nu_p(f(x)) = \ell_p$ and $\ell_p$ be the maximum value it attains. We claim that \begin{align*} n = \prod_{p \le 10^{100}} p^{\ell_p} \\ m \equiv x_p \pmod{p^{\ell_p}} \; \text{for all} \; p \le 10^{100}\end{align*} work for $(m, n)$. We note that there exists an $m$ satisfying that condition by CRT. Take a value $L$ and note that $\nu_p(f(a))$ can be found by directly using the given equation. Note that \begin{align*} \operatorname{min}(\nu_p(f(L)), \nu_p(f(x_p))) = \nu_p(f(L)) = \operatorname{min}(\ell_p, \nu_p(L-x_p))\end{align*}Now note that with the given values of $m$ and $n$, we have \begin{align*} \nu_p(f(L)) = \operatorname{min}(\nu_p(L-\operatorname{lcm} \{x_p\}), \nu_p(n)) \\ = \operatorname{min}(\nu_p(L-x_p), \ell_p) \end{align*}so we are done.

Call the primes less than $10^{100}$ in increasing order, $p_1$, $p_2$, $\dots$, $p_{n}$. Where $n$ is the number of primes less than $10^{100}$. Call the smallest positive $x$ such that $\nu_{p_i} (f(x))$ is maximized $x_{p_i}$ for each prime $p_i$. We have $$\nu_{p_i}(\gcd(f(x_{p_i}), f(x + k \cdot p^{\nu_{p_i} f(x_{p_i})} )) = \nu_{p_i} ( \gcd(f(x_{p_i}), k \cdot p^{\nu_{p_i} f(x_{p_i})} ) ) = \nu_{p_i} ( f(x_{p_i}))$$$$\implies \nu_{p_i} (f(x + k \cdot p^{\nu_{p_i} f(x_{p_i})} )) = \nu_{p_i} (f(x_{p_i}))$$So by CRT there exists a negative value of $x$ call it $x_{\text{ook}}$ such that for each prime $\nu_{p} f(x_{\text{ook}})$ is maximized. Now if $\nu_{p_{i}}(y) = k < \nu_{p_{i}} ( f(x_{\text{ook}}))$ then $$\nu_{p_i} (\gcd(f(x_{\text{ook}}), f(x_{\text{ook}} + y))) = \nu_{p_i}(\gcd(f(x_{\text{ook}}), y)) = \nu_{p_i}(y)$$So $f(x) = \boxed{ \gcd \left( x - x_{\text{ook}}, \prod_{i=1}^n p_i^{\nu_{p_i} ( f(x_{\text{ook}}))} \right)}$

Here's a nice solution which doesn't look at the $\nu_p$: Let $x_0$ be such that $f(x_0)$ is the maximum value of $f$ over all possible inputs, which exists as $f$ is upper bounded. We begin by proving the following Claim 1: $f(x)\mid f(x_0)$ for all $x$ Notice that $f(x)\mid f(x+kf(x))$ $\forall k$ as we have $\gcd(f(x), x-(x+kf(x))=\gcd(f(x), -kf(x))=f(x)$ so $\gcd(f(x),f(x+kf(x))=f(x)$. The key idea now is to prove that there exist $a, b$ such that $x+af(x)=x_0+bf(x_0)$. By rearranging the terms, we obtain $$ af(x)-bf(x_0) = x_0-x$$but we have $\gcd(f(x_0), f(x))\mid x_0-x$ so this is just Bézout's identity. To finish, note that by the previous observation there exists a $n$ such that $f(x)\mid f(n)$ and $f(x_0)\mid f(n)$. However, we have $f(n)\leq f(x_0)$ by definition, hence $f(n)=f(x_0)$, from which the result is immediate. We know that $$\gcd(f(x_0), f(y))=\gcd(f(x_0), x_0-y)$$for all $y$, but by Claim 1 $\gcd(f(x_0), f(y))=f(y)$, so this rewrites to $$f(y)=\gcd(f(x_0), x_0-y)$$from where the choices $n=f(x_0)$ and $m=-x_0$ finish the problem.