求证正整数a,b满足a!b! | (a,b)(a+b-1)!及思路正确性咨询

首先得明确：你的推导方向是错误的，核心问题出在这一步——“若假设a!b! | (a+b-1)!，则可推出a!b! | a、a!b! | b”。这完全不符合整除的基本逻辑：如果整数c整除d，不能直接得出c整除d的某个因子，除非c和d的其他因子互质，但这里a!b!和(a+b-1)!中除了a、b之外的部分显然不与a!b!互质。举个简单例子：a=3，b=2，a!b!=12，(a+b-1)! =24，12整除24，但你显然不能说12整除3或者12整除2，这就直接推翻了你的推论。

接下来我们回到原命题，给出正确的证明思路：

原命题求证：对于正整数a、b，有a!b! 整除 (a,b)(a+b-1)!，其中(a,b)是a和b的最大公约数 #

我们可以用素因子分解法来证明：对于任意素数p，只需证明p在a!b!中的指数 ≤ p在(a,b)(a+b-1)!中的指数即可（这是整除的充要条件）。

用到的工具：Legendre公式 #

对于正整数n和素数p，n!中p的指数为：
v_p(n!) = Σ_{k=1}^∞ floor(n/p^k)
其中floor(x)表示不超过x的最大整数。

证明步骤： #

设d=(a,b)，令v_p(d)=s（即p^s是p整除d的最高次幂），我们需要证明：
v_p(a!) + v_p(b!) ≤ v_p(d) + v_p((a+b-1)!)

展开后即：
Σ_{k=1}^∞ floor(a/p^k) + Σ_{k=1}^∞ floor(b/p^k) ≤ s + Σ_{k=1}^∞ floor((a+b-1)/p^k)

整理得：
Σ_{k=1}^∞ [floor(a/p^k) + floor(b/p^k) - floor((a+b-1)/p^k)] ≤ s

现在分析求和中的每一项：

1. 当k ≤ s时：
   因为p^{s整除d，而d整除a和b，所以p}k整除a和b，即a/p^k和b/p^k都是整数。此时：
   floor(a/p^k) = a/p^k，floor(b/p^k)=b/p^k
floor((a+b-1)/p^k) = floor( (a+b)/p^k - 1/p^k ) = (a+b)/p^k -1（因为1/p^k ≤1，且(a+b)/p^k是整数）
   所以这一项的值为：
   a/p^k + b/p^k - [(a+b)/p^k -1] = 1
   共有s个这样的项，和为s。

2. 当k > s时：
   此时p^{k不整除d，结合d=(a,b)的定义，a和b中至少有一个不被p}k整除。分两种情况：

   • 若其中一个数（比如a）被p^{k整除，则另一个数（b）不被p}k整除（否则p^{k会整除d，与k>s矛盾）。此时`floor(a/p^k)`是整数，`floor(b/p^k)`是小于b/p}k的整数，而floor((a+b-1)/p^k) = floor(a/p^k + b/p^k - 1/p^k)，由于b/p^{k的小数部分小于1，减去1/p}k后仍小于1，因此这一项的值为0。
   • 若a和b都不被p^k整除，结合(a,b)=d，可推导出a/p^k + b/p^k的小数部分小于1（或等于1，但此时减去1/p^k后小数部分仍小于1），因此floor(a/p^k)+floor(b/p^k) = floor((a+b)/p^k)或floor((a+b)/p^k)-1，无论哪种情况，这一项的值都为0。

综上，所有k>s的项的和为0，整个求和式的结果等于s，恰好等于v_p(d)，因此不等式成立。

由于对于任意素数p，p在a!b!中的指数都不超过在(a,b)(a+b-1)!中的指数，因此a!b!整除(a,b)(a+b-1)!，原命题得证。

内容的提问来源于stack exchange，提问作者Sandeep Gautam