第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

。

第 5/7 步：借助 5^n - 1 估计 2 的幂

上一步下一步

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

详细分析

由第3步， $f(5)=1$ ，故 $P(n,5)$ 给出 $f(n)\mid5^n-f(5)^{f(n)}=5^n-1$ 。由升幂引理(LTE)(因 $5\equiv1\pmod4$ )，对每个 $n$ 都有 $v_2(5^n-1)=v_2(n)+2$ 。由于 $f(n)$ 是整除 $5^n-1$ 的 $2$ 的幂，这给出 $f(n)\le2^{v_2(n)+2}=4\cdot2^{v_2(n)}\le4n$ (因 $2^{v_2(n)}\le n$ )。连同 $f=\mathrm{id}$ 情形的平凡估计( $f(n)=n\le4n$ )，每个 bonza 函数都满足 $f(n)\le4n$ ，故 $c=4$ 可行。