MathLabs

第3問

N\mathbb{N} を正の整数全体の集合とする。すべての正の整数 aa および bb に対して f(a)f(a) が ba−f(b)f(a)b^a-f(b)^{f(a)} を割り切るとき、関数 f:N→Nf:\mathbb{N}\to\mathbb{N} は bonza であるという。すべての bonza 関数 ff およびすべての正の整数 nn に対して f(n)≤cnf(n)\le cn が成り立つような、最小の実数定数 cc を求めよ。
ステップ 5/7: 5^n - 1 を用いて 2 のべきを評価する
前のステップ次のステップ
v2(5n−1)=v2(n)+2 ⟹ f(n)≤2v2(n)+2≤4nv_2(5^n-1)=v_2(n)+2\ \Longrightarrow\ f(n)\le2^{v_2(n)+2}\le4n
詳しい解説

ステップ3より f(5)=1f(5)=1 なので、P(n,5)P(n,5) より f(n)∣5n−f(5)f(n)=5n−1f(n)\mid5^n-f(5)^{f(n)}=5^n-1。指数持ち上げ補題(LTE)により(5≡1(mod4)5\equiv1\pmod4 なので)v2(5n−1)=v2(n)+2v_2(5^n-1)=v_2(n)+2 がすべての nn で成り立つ。f(n)f(n) は 5n−15^n-1 を割り切る 22 のべきなので、f(n)≤2v2(n)+2=4⋅2v2(n)≤4nf(n)\le2^{v_2(n)+2}=4\cdot2^{v_2(n)}\le4n が得られる(2v2(n)≤n2^{v_2(n)}\le n のため)。f=idf=\mathrm{id} の場合の自明な評価(f(n)=n≤4nf(n)=n\le4n)と合わせて、すべての bonza 関数が f(n)≤4nf(n)\le4n を満たすので c=4c=4 は有効である。