第3题

设

\mathbb{N}

表示正整数集合。若一个函数

f:\mathbb{N}\to\mathbb{N}

对任意正整数

a

和

b

，都有

f(a)

整除

b^a-f(b)^{f(a)}

，则称该函数为 bonza 函数。求最小的实常数

c

，使得对于所有 bonza 函数

f

以及所有正整数

n

，均有

f(n)\le cn

。

第 4/7 步：f(n) 总是 2 的幂

上一步下一步

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

详细分析

假设某个 $n$ 使奇素数 $p$ 整除 $f(n)$ ;那么(假设 $f\ne\mathrm{id}$ ，这是仍需估计的情形)利用第3步， $P(n,p)$ 给出 $f(n)\mid p^n-f(p)^{f(n)}=p^n-1$ ，特别地 $p\mid p^n-1$ ，但 $p\mid p^n$ 使这不成立。因此没有奇素数能整除 $f(n)$ ，即对每个 $n$ ， $f(n)$ 都是 $2$ 的幂。结合第1步( $f(n)\mid n^n$ )，若 $n$ 为奇数则 $n^n$ 也是奇数，故整除它的 $2$ 的幂只能是 $1$ ，从而对所有奇数 $n$ 都有 $f(n)=1$ 。