Problem 3.   Let $\mathbb{N}$ denote the set of positive integers. A function $f\colon\mathbb{N}\to\mathbb{N}$ is said to be $bonza$ if
\[ f(a) \bigm| b^a - f(b)^{f(a)} \quad\text{for all positive integers }a,b. \]Determine the smallest real constant $c$ such that
\[ f(n) \le cn \quad\text{for all bonza functions }f\text{ and all }n\in\mathbb{N}. \]

Solution 1Solution 2Solution 3

Solution 1 Let $P(m,n)$ denote the assertion. We start with some easy observations.
  • $P(n,n)$ gives $f(n) \mid n^n$ which immediately implies $f(1)=1$.
  • $f(p)$ is a power of $p$ for all primes $p$.
  • Also as $\operatorname{rad}(f(n)) \mid \operatorname{rad}(n)$, we have $(m,n)=1$ means $(f(m),n)=(f(m),f(n))=1$.
Claim: If $p \mid f(p)$ for infinitely many $p$, then $f$ is identity.
Proof: By Fermat's Little theorem and $P(p,n)$ we have $p \mid n-f(n) \implies f(n)=n$. $\square$

Hence assume for all large $p$, we have $f(p)=1$. Now we only care about these large primes.

Claim: $f(n) \mid m^n-1$ for all $\gcd(m,n)=1$.
Proof: By Dirichlet's theorem choose a prime $p \equiv m \pmod {n^n}$ such that $\gcd(m,n)=1$. Then $P(n,p)$ gives $f(n) \mid p^n-1 \implies f(n) \equiv m^n-1$. $\square$

Claim: $f(2n+1)=1$.
Proof: Now this obviously gives us that $f(n) \mid (-1)^n-1$ and so $f(2n+1) \mid 2$. Also $f(2n+1) \mid 2^{2n+1}-1$ and hence $f(2n+1)=1$. $\square$

Claim: $f(2n)$ is a power of $2$. Say $f(2n)=2^{g(n)}$.
Proof: By $P(2n,2m+1)$ we have $f(2n) \mid (2m+1)^{2n}-1$ for all $m$ and $n$. Hence $\gcd(f(2n),2m+1)=1$ and so $\operatorname{rad}(f(2n)) \mid 2$. $\square$

Now finally we have \begin{align*} 2^{g(n)} \mid 3^{2n}-1 \overset{\text{LTE}}{\implies} g(n) \le \nu_2(n)+3 \implies & f(2n)=2^{g(n)} \le 4 \cdot 2^{\nu_2(2n)} \le 4(2n) \implies c \le 4 \end{align*}To show this is sharp just have say \[f(n)=\begin{cases} 1 \text{ if $n$ is odd} \\ 16 \text{ if $n=4$} \\ 2 \text{ otherwise} \end{cases}\].

Hence the answer is $\boxed{c=4}$
Solution 2 The answer is $\boxed{c=4}$. A construction is $f(n)=\begin{cases}1&n\equiv 1\pmod 2\\4&n\equiv 2\pmod 4\\16&n\equiv 0\pmod 4\end{cases}$ which works by casework on $a,b\pmod 4$.

Now we bound. The main claim is that for prime $p$, either $p$ does not divide anything in the image of $f$, or $f$ is the identity $\pmod p$. To show this, suppose $p\mid f(k)$ for some $k$. Then $P(k,b)$ implies $p\mid b\iff p\mid f(b)$. Thus $p\mid f(p)$. Notice that $P(p,p)$ gives $f(p)\mid p^p$, so notably this gives $f(p)\equiv 1\pmod{p-1}$. Thus $P(p,b)$ gives $p\mid b^p-f(b)^{f(p)}$, which is congruent to $b-f(b)\pmod p$ by Fermat's little theorem. Thus $f$ is the identity $\pmod p$, as desired.

Next we claim that for an odd prime $q$ we have $f(q^n)\mid q^{n+1}$. To do this, from $f(q^n)\mid (q^n)^{q^n}$ we may set $f(q^n)=q^k$. Then we pick $b$ to be prime such that $b\equiv q+1\pmod{q^2}$, which exists by Dirichlet. Then $f(b)$ is a power of $b$, which are all $1\pmod q$. Now $P(q^n,b)$ gives $q^k\mid b^{q^n}-f(b)^{q^k}$. However we see $f(b)^{q^{k-1}}\equiv 1\pmod q^k$, so we have $q^k\mid b^{q^n}-1$. By LTE, we see $k\le\nu_q(b-1)+\nu_q(q^n)=1+n$, as desired.

Now suppose there exists an odd prime $p$ that divides something in the image of $f$. This implies $f$ is the identity $\pmod p$. Choose any prime $q$ such that $q\not\equiv 1\pmod p$, which there are infinitely many of by Dirichlet. Then $f(q)\in\{1,q,q^2\}$ but $f(q)\equiv q\pmod p$, so $f(q)=q$. Thus $q$ divides something in the image of $f$, so $f$ is the identity $\pmod q$. Thus $f$ is the identity mod infinitely many primes, so it is the identity $f(n)=n$. This indeed satisfies $f(n)\le 4n$.

Thus we may assume $2$ is the only prime that may appear. Let $a=m\cdot 2^n$ for $m$ odd, and let $f(a)=2^k$. Then $P(a,3)$ gives $2^k\mid 3^{m\cdot 2^n}-1$, since $f(3)$ is odd (if it was even, then $2$ does in fact appear, so $f$ is the identity $\pmod 2$, contradiction). Thus LTE gives $k\le\nu_2(2)+\nu_2(4)-1+\nu_2(m\cdot 2^n)=n+2$, so $f(a)\le 4a=m\cdot 2^{n+2}$, finishing.
Solution 3

Call the given equation $(a,b) : f(a) | b^a - f(b)^{f(a)}$.

Plugging in $(a,a)$, we get $f(a) | a^a$. This gives $f(1) = 1$ for starters. Moreover, we have $rad(f(n)) | rad(n)$ for all $n$. Call this property (1)

Next step: what if $f(p) = 1$ for all primes $p$? I claim that the only possibility now is $f(n) = 1$ for all $n$. Indeed:
take your $a>1$ s.t. $f(a) \neq 1$. We now know there exists a prime $q | a$ s.t. $q |f(a)$ aswell from (1). Now, plugging in $(a,q)$ gives us $q | f(a) | q^a - f(q)^{f(a)} = q^a - 1$. Now $q|q^a - 1$ is a clear contradiction.
Therefore the only case here is $f(n) = 1$ for all $n$ (which works, but we don't care about it).

Now, call $S$ the set of primes $q$ s.t. $f(q) = 1$ and call $T$ the other primes. Notice that for all primes $p$ in $T$ we have $p|f(p)$ due to (1).

Substituting $(p,q)$ gives us $f(p) | q^p - f(q)^f(p)$. If we now take $p \in T$ and $q \in S$ this gives us


\[p | q^p - 1\]

and Fermat gives us


\[p | q - 1.\]

This should hold for all primes $p \in T$ and $q \in S$. In particular, we have, for all $p \in T$ and for all $q \in S$, $p\le q$ and thus also $\max{T} \le \min{S}$.

If $S$ is empty, we are in the case above, so suppose $S$ isn't empty. In this case, there are only finitely many primes in $T$ (as $p \le \min S$ for all $p \in T$). There are two cases now:
1) $T$ isn't empty. We split in two small cases again:
a) The smallest prime in $T$ isn't $2$. This implies $3 \in T$. If so, then $3 | q-1$ for all primes $q \in S$. But since all primes bigger than $\min S$ are in $S$, all the primes $\equiv 2 \pmod 3$ bigger than this number are also in $S$! And we know that there are infinitely many such prime numbers, contradiction.

b) Now, suppose $T = \{2\}$. We now have $f(p) = 1$ for all odd primes $p$. It is easy to see that $f(n)$ is a power of two for all $n$ now. If not, there is a prime $q$ dividing $f(n)$ and thus $n$. But plugging in $(n,q)$ gives $q|f(n) |q^n - 1$, contradiction.

In particular, $f(n) = 1$ for all odd $n$. Next, take $n$ even and take $q=13$ odd.
Notice that we need


\[f(n) | 13^{n} - 1.\]

Now, as $\nu_2(13^{n} - 1) = \nu_2(13+1) + \nu_2(13-1) + \nu_2(n) - 1 = 2 + \nu_2(n)$ due to LTE lemma. The reason we chose $q=13$ is because it minimizes $\nu_2(q+1) + \nu_2(q-1)$ over all primes $q$.
This directly implies that $f(n) \le 4n$ as $f(n)$ is a power of two.

If we now write any integer $n$ as $2^{a}b$, with gcd$(2,b) = 1$, and choose $f(2^a b) = 2^a$ for all $n$, but we take $f(2^{67}) = 2^69$, it is an elementary check that this works. Thus, $c \ge 4$.

Finally, suppose that $T$ is empty. In this case, we have $p|f(p)$ for all primes $p$.
First, notice that $p-1 | f(p) - 1$ as $f(p)$ is a power of $p$ due to (1).
Furthermore, substituting $(p,n)$ with $p$ prime, gives us


\[f(p) | n^p - f(n)^f(p)\]

and thus,


\[n \equiv n^p \equiv f(n)^f(p) \equiv f(n) \pmod p.\]

In other words
$p | f(n) - n$ for all primes $p$. This implies that $f(n) = n$ for all $n$ clearly, just by taking a prime $p$ bigger than $|f(n) - n|$.

We have done every case. Every Bonza function is one of the above. Of course other constructions work for the $f(n) \le 4n$ case, but they can all be categorized similarily. All of them should satisfy $f(n) \le 4n$ either way. This means that $c = 4$ is the best construction. We are done.

Solution 4 Solution4