Problem: A function $f \colon \NN \to \NN$ is said to be \emph{bonza} if
\[ f(a)\quad\text{divides}\quad b^a-f(b)^{f(a)} \]
for all positive integers $a$ and $b$.

Determine the smallest real constant $c$ such that $f(n) \leq cn$
for all bonza functions $f$ and all positive integers $n$.

Solution: The answer is $c=4$.

Let $P(a,b)$ denote the given statement $f(a) \mid b^a - f(b)^{f(a)}$.
\begin{claim*}
  We have $f(n) \mid n^n$ for all $n$.
\end{claim*}
\begin{proof}
  Take $P(n,n)$.
\end{proof}

\begin{claim*}
  Unless $f = \id$, we have $f(p) = 1$ for all odd primes $p$.
\end{claim*}
\begin{proof}
  Consider any prime $q$ with $f(q) > 1$.
  Then $f(q)$ is a power of $q$, and for each $n$ we get
  \[ P(q,n) \implies q \mid f(q) \mid n^q - f(n)^{f(q)}. \]
  Fermat's little theorem now gives
  $n^q \equiv n \pmod q$ and $f(n)^{f(q)} \equiv f(n) \pmod q$
  (since $f(q)$ is a power of $q$), and therefore $q \mid n - f(n)$.
  Hence, unless $f$ is the identity function,
  only finitely many $q$ could have $f(q) > 1$.

  Now let $p$ be any odd prime,
  and let $q$ be a large prime such that $q \not\equiv 1 \pmod p$
  (possible for all $p > 2$, say by Dirichlet).
  Then
  \[ P(p,q) \implies f(p) \mid q^p - 1^p. \]
  The RHS is $q^p - 1 \equiv q - 1 \not\equiv 0 \pmod p$, so $f(p) = 1$.
\end{proof}

\begin{claim*}
  We have $f(n) \mid 2^\infty$ for all $n$.
\end{claim*}
\begin{proof}
  If $p \mid f(n)$ is odd then $P(n,p)$ gives $p \mid f(n) \mid p^n-1^n$,
  contradiction.
\end{proof}
(In particular, we now know $f(n) = 1$ for all odd $n$, though we don't use this.)

\begin{claim*}
  We have $f(n) \le 2^{\nu_2(n)+2}$ for all $n$.
\end{claim*}
\begin{proof}
  Consider $P(n,5) \implies f(n) \mid 5^n - 1^n$.
  It's well-known that $\nu_2(5^n-1) = \nu_2(n)+2$ for all $n$.
\end{proof}
This immediately shows $f(n) \le 4n$ for all $n$, hence $c=4$ in the problem statement works.

For the construction, the simplest one seems to be
\[
  f(n) = \begin{cases}
    1 & n \text{ odd} \\
    16 & n = 4 \\
    2 & n \text{ even}, n \neq 4
  \end{cases}
\]
which is easily checked to work and has $f(4) = 16$.

\begin{remark*}
  With a little more case analysis we can classify all functions $f$.
  The two trivial solutions are $f(n) = n$ and $f(n) = 1$;
  the others are described by writing $f(n) = 2^{e(n)}$ for any function $e$ satisfying
  \begin{itemize}
    \ii $e(n) = 0$ for odd $n$;
    \ii $1 \le e(2) \le 2$;
    \ii $1 \le e(n) \le \nu_2(n)+2$ for even $n > 2$.
  \end{itemize}
  This basically means that there are almost no additional constraints
  beyond what is suggested by the latter two claims.
\end{remark*}