Problem: Let $f \colon \ZZ \to \{1, 2, \dots, 10^{100}\}$
be a function satisfying
\[ \gcd(f(x), f(y)) = \gcd(f(x), x-y) \]
for all integers $x$ and $y$.
Show that there exist positive integers $m$ and $n$ such that
$f(x) = \gcd(m + x, n)$ for all integers $x$.

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 \opname{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.
\begin{claim*}
  For any $p \in \mathcal P$, we have
  \[ \nu_p(f(x)) = \min(\nu_p(x - c_p), e_p). \]
\end{claim*}
\begin{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.
\end{proof}

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 \ZZ$, as desired.

\begin{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.
\end{remark*}

\begin{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$.
\end{remark*}