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 4 of 7: f(n) is always a power of 2

Previous step Next step

f(n)\ \text{is a power of }2\ \text{for every }n,\quad f(n)=1\ \text{for odd }n

Detailed analysis

Suppose an odd prime $p$ divides $f(n)$ for some $n$ ; then (assuming $f\ne\mathrm{id}$ , the only case left to bound) $P(n,p)$ gives $f(n)\mid p^n-f(p)^{f(n)}=p^n-1$ using step 3, so in particular $p\mid p^n-1$ , which is false since $p\mid p^n$ . Hence no odd prime divides $f(n)$ , i.e. $f(n)$ is a power of $2$ for every $n$ . Combined with step 1 ( $f(n)\mid n^n$ ), if $n$ is odd then $n^n$ is odd, so the power of $2$ dividing it must be $1$ , giving $f(n)=1$ for all odd $n$ .