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 2 of 7: Only finitely many primes q can have f(q) > 1

Previous step Next step

f(q)>1\ \Longrightarrow\ q\mid n-f(n)\ \text{for all }n\ \Longrightarrow\ \text{unless }f=\mathrm{id},\ \text{only finitely many primes }q\ \text{have }f(q)>1

Detailed analysis

By the previous step $f(q)\mid q^q$ , so if $f(q)>1$ then $f(q)$ is a power of $q$ . Then $P(q,n)$ gives $q\mid f(q)\mid n^q-f(n)^{f(q)}$ ; by Fermat's little theorem $n^q\equiv n\pmod q$ , and iterating Fermat shows $f(n)^{f(q)}\equiv f(n)\pmod q$ (as $f(q)$ is a power of $q$ ), so $q\mid n-f(n)$ for every $n$ . If this held for infinitely many primes $q$ , then $n-f(n)$ would be divisible by arbitrarily large primes for every $n$ , forcing $f(n)=n$ for all $n$ , i.e. $f=\mathrm{id}$ . So unless $f=\mathrm{id}$ , only finitely many primes $q$ satisfy $f(q)>1$ .