IMO 2025 · Problem 3

Let \(\mathbb{N}\) denote the set of positive integers. A function \(f:\mathbb{N}\to\mathbb{N}\) is said to be bonza if \[ f(a)\text{ divides }b^a-f(b)^{f(a)} \] for all positive integers \(a\) and \(b\).

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

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{c=4}. \]

Solution

Let \(f\) be bonza. Taking \(b=a\) gives \[ f(a)\mid a^a. \tag{1} \]

We first prove that either \(f(n)=n\) for every \(n\), or every value of \(f\) is a power of \(2\), including \(2^0=1\).

Let \(\mathcal P\) be the set of primes dividing at least one value of \(f\). For \(p\in\mathcal P\), choose \(a\) such that \(p\mid f(a)\). Substituting \(b=p\) into the defining condition and reducing modulo \(p\) gives \[ p\mid f(p)^{f(a)}, \] so \(p\mid f(p)\). By (1), \(f(p)\mid p^p\), and consequently \[ f(p)=p^k \] for some positive integer \(k\).

Now substitute \(a=p\) into the defining condition. Reducing modulo \(p\) and applying Fermat’s little theorem gives, for every positive integer \(b\), \[ b\equiv b^p\equiv f(b)^{p^k}\equiv f(b)\pmod p. \tag{2} \]

Suppose \(f\) is not the identity. Choose \(t\) with \(f(t)\ne t\). By (2), every prime in \(\mathcal P\) divides the nonzero integer \(f(t)-t\), so \(\mathcal P\) is finite.

If \(\mathcal P\) is empty, all values of \(f\) are \(1\), as desired. Otherwise, put \[ D=\prod_{p\in\mathcal P}p. \] Here \(D\ge2\), so \(D-1\) is positive. Every prime divisor of \(f(D-1)\) would divide \(D\), by the definition of \(\mathcal P\), and would also divide \(D-1\), by (1). This is impossible, so \[ f(D-1)=1. \] Applying (2) with \(b=D-1\), we obtain \[ D\mid f(D-1)-(D-1)=2-D. \] Thus \(D\mid2\), whence \(D=2\). Therefore \(\mathcal P=\{2\}\), proving the claimed restriction.

We now establish the upper bound. If \(f\) is the identity, it is immediate. Otherwise, every value of \(f\) is a power of \(2\). For odd \(n\), equation (1) forces \(f(n)=1\). In particular, \(f(3)=1\). Taking \(b=3\) in the defining condition yields \[ f(n)\mid 3^n-1. \tag{3} \]

For even \(n\), write \[ n=2^r u,\qquad r\ge1,\quad u\text{ odd}. \] We claim that the largest power of \(2\) dividing \(3^n-1\) is \(2^{r+2}\). Indeed, \[ 3^n-1=(3^{2^r}-1) \left(1+3^{2^r}+\cdots+3^{(u-1)2^r}\right), \] and the second factor is odd. Also, \[ 3^{2^r}-1 =8\prod_{j=1}^{r-1}\left(3^{2^j}+1\right). \] Each factor in the product is congruent to \(2\) modulo \(8\), since \(3^{2^j}\equiv1\pmod8\) for \(j\ge1\). Thus it contributes exactly one factor of \(2\). This also covers \(r=1\), when the product is empty.

Since \(f(n)\) is a power of \(2\), (3) now implies \[ f(n)\le 2^{r+2}=4\cdot2^r\le4n. \] Together with the odd case, this proves the required bound for every bonza function.

To show that the constant cannot be smaller, define \[ g(n)= \begin{cases} 16,&n=4,\\ 2,&n\text{ is even and }n\ne4,\\ 1,&n\text{ is odd}. \end{cases} \] We verify the bonza condition for all positive integers \(a,b\).

  • If \(a\) is odd, then \(g(a)=1\), so the condition is automatic.
  • If \(a\) is even and \(a\ne4\), then \(g(a)=2\). Since \(g(b)\) and \(b\) have the same parity, \[ b^a\equiv b\equiv g(b)^2\pmod2. \]
  • If \(a=4\), then \(g(a)=16\). For even \(b\), both \(b^4\) and \(g(b)^{16}\) are divisible by \(16\). For odd \(b\), we have \(g(b)=1\) and \(b^4\equiv1\pmod{16}\): indeed, \(b^2=8s+1\) for some integer \(s\), whose square is congruent to \(1\) modulo \(16\).

Thus \(g\) is bonza. Since \[ g(4)=16=4\cdot4, \] every admissible constant satisfies \(c\ge4\). Combined with the upper bound, this proves \(\boxed{c=4}\).

The solution was checked against the official IMO shortlist solutions.