ecaeca 发表于 2025-01-18 09:44回复 1楼 adda 的帖子 我觉得有两个小地方可以改进，一个是在2:40左右讲两个大整数的gcd的时候，应该说明把它们因式分解是非常困难非常耗时的。这也是Euclidean Algorithm的优势。 第二是这整个方法就叫Euclidean Algorithm，前面讲的gcd(a,b)=gcd(a-b,b)只能被认为是把Euclidean Algorithm的一步再分解成了一个个小步。后面的gcd(a,b)=gcd(r,b)不应该叫Extended Euclidean Algorithm而应该就是Euclidean Algorithm
欢迎提建议。
我觉得有两个小地方可以改进，一个是在2:40左右讲两个大整数的gcd的时候，应该说明把它们因式分解是非常困难非常耗时的。这也是Euclidean Algorithm的优势。
第二是这整个方法就叫Euclidean Algorithm，前面讲的gcd(a,b)=gcd(a-b,b)只能被认为是把Euclidean Algorithm的一步再分解成了一个个小步。后面的gcd(a,b)=gcd(r,b)不应该叫Extended Euclidean Algorithm而应该就是Euclidean Algorithm
谢谢指点。刚google了一下，确实extended euclidean algorithm是别的意思。看来AoPS Intro to Number Theory 书上这部分写的是不准确的。
既然是AOPS的书这么写的，那估计很多人都认同这个叫法了。那你这么写也是没问题的。
还是要严格一些 更新了video