Part 1 内容不准确:Euclid 算法结论证明
GitPinkRabbit opened this issue · 2 comments
GitPinkRabbit commented
对 gcd(a, b) = gcd(b, a mod b) 的证明中,“当 b ≠ 0 时,有关于整除的结论” 后未提到 d 是 b 的因数(frame 45)
GitPinkRabbit commented
事实上,证明 gcd(a, b) = gcd(b, a mod b) 时应该从两方面对称地说明,即:
- 先说明基于 d | b 的大前提下,d | x 可以推出 d | (x + k · b),其中 k 可以取任意整数
- 令 q = [a / b] 和 r = a mod b,注意到 a - q · b = r 和 r + q · b = a 的对称性
- 结合前两点,说明 d | a 与 d | r 可以互相推出,即它们等价(在 d | b 的前提下)
- 即,d 为 a, b 的公因数,等价于 d 为 (a mod b), b 的公因数
- 结合 d | a 且 d | b 等价于 d | gcd(a, b),有 d | gcd(a, b) 等价于 d | gcd(b, a mod b)
- 最后,gcd(a, b) = gcd(b, a mod b)
GitPinkRabbit commented
于 e6e818f 中修复