阶乘与平方数的整除性

嘿，这个问题我之前也琢磨过，咱们一步步来拆解～

首先，先从小的正整数试起，看看哪些n满足n²能整除n!：

• n=1：1²=1，1! =1，显然整除，没问题；
• n=2（质数）：4整除2？2!是2，不行；
• n=3（质数）：9整除6？也不行；
• n=4（质数平方）：16整除24？24÷16=1.5，不满足；
• n=6（合数，两个不同质因子）：36整除720？720÷36=20，完美满足；
• n=9（质数平方，3²）：81整除362880？算一下，362880÷81=4480，也满足。

接下来咱们总结规律：

1. 质数的情况 #

如果n是质数p，那p!里只包含一个p的因子（就是p本身），而p²需要两个p的因子，所以所有质数都不满足条件。这里其实可以结合威尔逊定理辅助理解：威尔逊定理说(p-1)! ≡ -1 mod p，意味着(p-1)! 不能被p整除，那p! = p*(p-1)! 里自然只有一个p的因子，所以p²肯定没法整除p!。

2. 合数的情况 #

合数里要分两种：

• n=4：这是唯一的例外。4=2²，4!里2的因子总数是floor(4/2)+floor(4/4)=2+1=3个，而4²=2⁴需要4个2的因子，3<4，所以不满足；
• 其他合数：不管是像6、10这样的多质因子合数，还是像9、25这样的≥3的质数平方，都满足条件。比如n=9=3²，9!里3的因子总数是floor(9/3)+floor(9/9)=3+1=4个，刚好等于9²需要的4个3的因子；n=8=2³，8!里2的因子总数是8+4+2+1=15个，远多于8²=2⁶需要的6个。

最终结论 #

正整数n满足n² | n! 的条件是：n=1，或者n是合数且n≠4（换句话说，n不是质数，也不等于4）。

备注：内容来源于stack exchange，提问作者rpmdoestuff