如何证明关于LCM的命题？求证当(a,b)=1时LCM(n/a,n/b)=n

嗨，这个问题用素因数分解的思路拆解就非常直观！咱们结合你给出的素因子设定一步步推导：

首先明确已知条件：

• gcd(a,b)=1（a和b互素）
• a和b都整除n，所以a、b的素因子只能是n的素因子，因此可以统一写成：
  • n的素因数分解：n = p₁^α₁ p₂^α₂ … p_k^α_k
  • a的素因数分解：a = p₁^β₁ p₂^β₂ … p_k^β_k，其中0 ≤ β_i ≤ α_i（因为a|n）
  • b的素因数分解：b = p₁^γ₁ p₂^γ₂ … p_k^γ_k，其中0 ≤ γ_i ≤ α_i（因为b|n）

关键推导步骤 #

1. 利用互素条件缩小指数范围
   因为gcd(a,b)=1，对于每个素因子p_i，gcd(p_i^β_i, p_i^γ_i)=1。这意味着β_i和γ_i不能同时大于0——换句话说，对每个i，要么β_i=0，要么γ_i=0（如果两者都≥1，gcd至少是p_i≥2，就不满足互素了）。

2. 计算n/a和n/b的素因数分解

   • n/a = p₁^(α₁-β₁) p₂^(α₂-β₂) … p_k^(α_k-β_k)
   • n/b = p₁^(α₁-γ₁) p₂^(α₂-γ₂) … p_k^(α_k-γ_k)

3. 求LCM的素因子指数
   最小公倍数的素因数分解规则是：每个素因子的指数取两个数中该素因子指数的最大值。即LCM(n/a, n/b)中p_i的指数为：

   max(α_i - β_i, α_i - γ_i) = α_i - min(β_i, γ_i)
   

   结合第一步的结论，min(β_i, γ_i)=0（因为β_i和γ_i必有一个为0），所以这个最大值就是α_i - 0 = α_i。

4. 得出结论
   LCM(n/a, n/b)的素因数分解就是p₁^α₁ p₂^α₂ … p_k^α_k = n，完美符合要证的结论！

解答你的疑问 #

你提到n/a和n/b都整除n，但为啥它们的LCM还是n？核心原因就是a和b互素：这保证了n的每个素因子，不会同时被a和b“分摊”——也就是说，n/a和n/b中至少有一个保留了该素因子的全部指数（比如如果a不含p_i，那n/a里p_i的指数就是α_i）。当取LCM时，所有素因子的指数都会被拉满到n的原始指数，最终结果自然就是n本身。

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