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)

divides

b^a-f(b)^{f(a)}

for all positive integers

a

and

b

. Determine the smallest real constant

c

such that

f(n)\le cn

for all bonza functions

f

and all positive integers

n

Step 1 of 7: The diagonal substitution a = b = n

Previous step Next step

f(n)\mid n^n\quad\text{for all }n

Detailed analysis

Write $P(a,b)$ for the statement $f(a)\mid b^a-f(b)^{f(a)}$ . Taking $P(n,n)$ gives $f(n)\mid n^n-f(n)^{f(n)}$ . Since $f(n)^{f(n)}$ is itself a multiple of $f(n)$ (as $f(n)\ge1$ ), adding it back shows $f(n)\mid n^n$ .