MathLabs

第3题

设 k≥14k\ge14 为整数,pkp_k 为严格小于 kk 的最大素数,可假设 pk≥3k/4p_k\ge3k/4。设 nn 为合数。证明:(a) 若 n=2pkn=2p_k,则 nn 不整除 (n−k)!(n-k)!;(b) 若 n>2pkn>2p_k,则 nn 整除 (n−k)!(n-k)!。
第 3/5 步:处理二的幂
n=2t (t≥5):n=4⋅2t−2,4,2t−2<n/3n=2^t\ (t\ge5):\qquad n=4\cdot2^{t-2},\qquad 4,2^{t-2}<n/3
详细分析

若 n=2tn=2^t,则 n>26n>26 迫使 t≥5t\ge5。两个不同因子 44 与 2t−22^{t-2} 的积为 nn,且二者都不超过 n/3n/3(包括最小情形 n=32n=32)。它们分别出现在 (n−k)!(n-k)! 中,故 nn 整除该阶乘。