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 3 of 7: Choosing a large clean prime q forces f(p) = 1

Previous step Next step

f\ne\mathrm{id}\ \Longrightarrow\ f(p)=1\ \text{for every odd prime }p

Detailed analysis

Assume $f\ne\mathrm{id}$ and let $p$ be any odd prime; by step 1, $f(p)$ is a power of $p$ , say $f(p)=p^m$ . Since only finitely many primes $q$ have $f(q)>1$ , choose a prime $q$ larger than all of them with $q\not\equiv1\pmod p$ (such $q$ exists since infinitely many primes avoid the single residue class $1\bmod p$ ), so $f(q)=1$ . Then $P(p,q)$ gives $f(p)\mid q^p-f(q)^{f(p)}=q^p-1$ . If $m\ge1$ then $p\mid f(p)\mid q^p-1$ , but Fermat's little theorem gives $q^p\equiv q\pmod p$ , so $q^p-1\equiv q-1\not\equiv0\pmod p$ by the choice of $q$ , a contradiction. Hence $m=0$ , i.e. $f(p)=1$ .