阶乘与斐波那契数列

前段时间有个读者问了一道题：

求所有的正整数𝑛，使得𝑛!能表示为两个斐波那契数之积．

这应该是前两年的一道国外赛题，具体出处记不太清了．主要的想法是说明这样的𝑛是有限的，可以通过质因子指数的估计和不等式放缩来证明．当然，关于斐波那契数列的性质也需要熟悉．

解： 设斐波那契数列为{𝐹_(𝑛)}：𝐹_(1)=𝐹_(2)=1，𝐹_(𝑛+2)=𝐹_(𝑛+1)+𝐹_(𝑛)．先证明以下四个引理：

引理1:𝐹_(𝑘)≥1.6^(𝑘−2)．

引理1的证明： 𝐹_(1)=1>1.6^(−1)，

若𝐹_(𝑘)≥1.6^(𝑘−2)，𝐹_(𝑘+1)≥1.6𝑘−1，则

公式：\begin{aligned} F_{k+2}=&F_k+F_{k+1}\\ \geq& 1.6{k-2}+1.6^{k-1}\\ =&1.6^{k-2}\times 2.6\\ >& 1.6^k \end{aligned}

引理2:公式：F_{3k}=5F_k^3+3\cdot(-1)^kF_k．

引理2的证明： 设𝛼=(1+√(5))/(2)，𝛽=(1−√(5))/(2)．则

公式：\begin{aligned} F_{3k}=&\dfrac{\alpha^{3k}-\beta^{3k}}{\sqrt{5}}\\ =&\dfrac{(\alpha^k-\beta^k)^3+3\alpha^k\beta^k(\alpha^k-\beta^k)}{\sqrt{5}}\\ =&5\left(\dfrac{\alpha^k-\beta^k}{\sqrt{5}}\right)^3+3\cdot(-1)^k\dfrac{\alpha^k-\beta^k}{\sqrt{5}}\\ =&5F_k^3+3\cdot(-1)^kF_k \end{aligned}

引理3: 若3^(𝑡)∣𝐹_(𝑘)，则4⋅3^(𝑡−1)∣𝑘．

引理3的证明： 容易验证𝑡=1和𝑡=2时的情形．若结论在𝑡时成立（𝑡≥2），考虑𝑡+1时的情况：

若3^(𝑡+1)∣𝐹_(𝑘)，则3^(𝑡)∣𝐹_(𝑘)，由归纳假设，有4⋅3^(𝑡−1)∣𝑘．设𝑚=(𝑘)/(3)，则𝑚为偶数．则由引理2:

公式：F_k=F_{3m}=5F_m^3+3F_m

由于3∣𝐹_(𝑘)，故3∣𝐹3𝑚，即3∣𝐹_(𝑚)．

于是𝑣_(3)(5𝐹3𝑚)>𝑣_(3)(3𝐹_(𝑚))．故

公式：v_3(F_k)=v_3(3F_m)=v_3(F_m)+1

由3^(𝑡+1)∣𝐹_(𝑘)知3^(𝑡)∣𝐹_(𝑚)，故4⋅3^(𝑡−1)∣𝑚，即4⋅3^(𝑡)∣𝑘．证毕．

引理4: 𝑛≥12时，𝑣_(3)(𝑛!)>(𝑛)/(3)．

引理4的证明： 𝑛>14时，

公式：\begin{aligned} v_3(n!)=&\sum_{k=1}^{\infty}\left[\dfrac{n}{3^k}\right]\\ \geq&\left[\dfrac{n}{3}\right]+\left[\dfrac{n}{9}\right]\\ \geq&\dfrac{n}{3}-\dfrac{2}{3}+\dfrac{n}{9}-\dfrac{8}{9}\\ =&\dfrac{n}{3}+\dfrac{n-14}{9}\\ \geq&\dfrac{n}{3} \end{aligned}

𝑛=12，13，14时，也容易验证成立．

回到原题．

若𝑛≥12时，存在𝑘，𝑙∈ℕ_(+)，使𝑛!=𝐹_(𝑘)⋅𝐹_(𝑙)．

则公式：4\leq \dfrac{n}{3}< v_3(n!)=v_3(F_kF_l)=v_3(F_k)+v_3(F_l)．

设𝑣_(3)(𝐹_(𝑘))=𝑥，𝑣_(3)(𝐹_(𝑙))=𝑦，则有𝑥+𝑦≥5，不妨设𝑦≥𝑥，则𝑦≥3．

则𝑘≥4⋅3^(𝑥−1)=3^(𝑥)+3^(𝑥−1)≥3^(𝑥)+1．

公式：l\geq 4\cdot 3^{y-1}=3^y+3^{y-1}\geq 3^y+9．

所以

公式：\begin{aligned} &2^{n(n-1)}>n^{n-1}>n!=F_kF_l\geq 1.6^{3^x-1}\cdot 1.6^{3^y+7}\\ =&1.6^{3^x+3^y+6}\geq 1.6^{2\cdot 3^{\frac{x+y}{2}}+6}> 1.6^{2\cdot 3^{\frac{n}{6}}+6}>2^{3^{\frac{n}{6}}+3} \end{aligned}

因此𝑛(𝑛−1)>3^((𝑛)/(6)+3)，矛盾．故𝑛≤11．

对1≤𝑛≤11的情况逐一验证可得：𝑛=1，2，3，4，6符合题意．其中

最后的放缩比较宽松，所以得到的范围还是挺大的，可以估计得更细一些，减少枚举量（毕竟11!太大了）．

文章最后再放一道相关题目，也是用质因子的指数来估计范围，从而证明一个不定方程只有有限组解．

（2019年IMO） 求所有正整数对(𝑘,𝑛)，满足𝑘!=(2^(𝑛)−1)(2^(𝑛)−2)⋯(2^(𝑛)−2^(𝑛−1))．