GitPinkRabbit/Number-Theory-in-Competitive-Programming

Part 1 内容不准确:Euclid 算法结论证明

GitPinkRabbit opened this issue · 2 comments

对 gcd(a, b) = gcd(b, a mod b) 的证明中,“当 b ≠ 0 时,有关于整除的结论” 后未提到 d 是 b 的因数(frame 45)

事实上,证明 gcd(a, b) = gcd(b, a mod b) 时应该从两方面对称地说明,即:

  1. 先说明基于 d | b 的大前提下,d | x 可以推出 d | (x + k · b),其中 k 可以取任意整数
  2. 令 q = [a / b] 和 r = a mod b,注意到 a - q · b = r 和 r + q · b = a 的对称性
  3. 结合前两点,说明 d | a 与 d | r 可以互相推出,即它们等价(在 d | b 的前提下)
  4. 即,d 为 a, b 的公因数,等价于 d 为 (a mod b), b 的公因数
  5. 结合 d | a 且 d | b 等价于 d | gcd(a, b),有 d | gcd(a, b) 等价于 d | gcd(b, a mod b)
  6. 最后,gcd(a, b) = gcd(b, a mod b)

e6e818f 中修复