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 5 of 7: Bounding the power of 2 via 5^n - 1

Previous step Next step

v_2(5^n-1)=v_2(n)+2\ \Longrightarrow\ f(n)\le2^{v_2(n)+2}\le4n

Detailed analysis

By step 3, $f(5)=1$ , so $P(n,5)$ gives $f(n)\mid5^n-f(5)^{f(n)}=5^n-1$ . By the lifting-the-exponent lemma (since $5\equiv1\pmod4$ ), $v_2(5^n-1)=v_2(n)+2$ for every $n$ . As $f(n)$ is a power of $2$ dividing $5^n-1$ , this gives $f(n)\le2^{v_2(n)+2}=4\cdot2^{v_2(n)}\le4n$ , since $2^{v_2(n)}\le n$ . Together with the trivial bound for $f=\mathrm{id}$ (where $f(n)=n\le4n$ ), every bonza function satisfies $f(n)\le4n$ , so $c=4$ works.