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 6 of 7: A construction attaining c = 4 exactly

Previous step Next step

f(n)=\begin{cases}1 & n\text{ odd}\\16 & n=4\\2 & n\text{ even},\,n\ne4\end{cases}\ \text{is bonza and has}\ f(4)=16=4\cdot4

Detailed analysis

Take $f(n)=1$ for odd $n$ , $f(4)=16$ , and $f(n)=2$ for even $n\ne4$ . This is bonza: if $a$ is odd, $f(a)=1$ divides anything; if $a=4$ , one checks $16\mid b^4-f(b)^{16}$ using that $b^4\equiv1\pmod{16}$ for odd $b$ , that $16\mid b^4$ and $16\mid2^{16}$ for even $b\ne4$ , and the case $b=4$ directly; if $a$ is even with $a\ne4$ , one checks $2\mid b^a-f(b)^2$ by parity in each case for $b$ . Since $f(4)=16=4\cdot4$ , this function shows the bound $f(n)\le4n$ cannot be improved, so $c=4$ is optimal.