https://youtu.be/yFyJZIVkKvw

欢迎提建议。

我觉得有两个小地方可以改进，一个是在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

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

谢谢指点。刚google了一下，确实extended euclidean algorithm是别的意思。看来AoPS Intro to Number Theory 书上这部分写的是不准确的。

既然是AOPS的书这么写的，那估计很多人都认同这个叫法了。那你这么写也是没问题的。

回复 4楼 ecaeca 的帖子

还是要严格一些

更新了video