作者alan23273850 (God of Computer Science)
看板Math
标题[数论] Extended Euclidean 算法求得的系数上界
时间Tue May 11 00:26:53 2021
各位板友大家好打给贺泰轧贺，小弟最近在复习数论，刚好遇到一个以前没学过但
很有趣的结论，它是说当 Extended Euclidean Algorithm
迭代到 ax + by = 0 的时候
会满足 |x| = b / gcd(a,b) 以及 |y| = a / gcd(a,b) 的结论，
由於我已经知道 |x| 和 |y| 都会在迭代过程中不严格递增，那麽透过上面那句话，
我就能间接知道 |x| 和 |y| 永远不会超过 b 和 a，不论 a 和 b 是否互质。
那麽要怎麽得到黄色那句话的结论呢？先感谢各位先进了！
附上已阅读参考资料：
https://www.wikiwand.com/en/Extended_Euclidean_algorithm
https://jeffhurchalla.com/2018/10/09/analysis-of-bounds-in-the-extended-euclide
an-algorithm/
#conclusion
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.194.139.84 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1620664017.A.FC8.html
※ 编辑: alan23273850 (123.194.139.84 台湾), 05/11/2021 00:34:34
1F：推 LPH66 : 可以证明过程中的 x, y 永远互质 05/11 00:44
2F：→ LPH66 : 那 = 0 的互质解就是给定的这一组 05/11 00:46
3F：→ LPH66 : 咦等等, 我想一下...我似乎搞错了一些东西 05/11 01:04
4F：→ LPH66 : OK, 想过了没错, 我以为我搞错矩阵行列了 XD 05/11 01:07
5F：→ alan23273850: 好的！感谢ＬＰＨ大大，我来想想怎麽证明１Ｆ 05/11 11:45
6F：→ alan23273850: 听起来会 reduce 到 if gcd(x1,y1) = gcd(x2,y2) =1 05/11 12:11
7F：→ alan23273850: then gcd(x1-x2*q) = gcd(y1-y2*q) = 1 for any q 05/11 12:11
8F：推 eikcaj102 : 05/11 12:37
9F：→ alan23273850: 欸... 结果我还是想不到怎麽证明１Ｆ 05/11 17:01
10F：→ alan23273850: 我现在是把系数用 1 和各种 qi 的线性组合表示，每 05/11 18:25
11F：→ alan23273850: 一轮确实都可以用辗转相除法得到 gcd=1 的结论，但 05/11 18:26
12F：→ alan23273850: 还没得到一个很一般性的推法 05/11 18:26
13F：→ alan23273850: 啊！我终於知道怎麽证了，它必须从(1,0)和(0,1)开始 05/11 20:37
14F：→ alan23273850: 然後证明後续的tuple作完辗转相除法的第一个步骤的 05/11 20:45
15F：→ alan23273850: 剩余tuple会跟前一个tuple的形式一样，就能证明gcd 05/11 20:46
16F：→ alan23273850: 会不变了！这个证法真的好妙，请大大收下我的膝盖！ 05/11 20:46
17F：推 LPH66 : 差不多是这样没错, 然而我会提矩阵是因为 05/11 23:15
18F：→ LPH66 : 推移的关系式可以用矩阵表示, 使得每一步都是乘上 05/11 23:16
19F：→ LPH66 : 一个大致上是 2x2 基本矩阵运算的矩阵 05/11 23:16
20F：→ LPH66 : 所要的不变量则就是这个矩阵的行列式, 开始是 1 05/11 23:16
21F：→ LPH66 : 在运算过程中它只会是正负 1, 但如果 x y 不互质 05/11 23:17
22F：→ LPH66 : 这个整数矩阵就会有大於 1 的行列式, 矛盾 05/11 23:18
我刚刚竟然又找到更好懂的教材＆表示方式！
https://www.staff.uni-mainz.de/pommeren/MathMisc/Euclid.pdf#page=3
他是用 |x(i+1)*y(i) - x(i)*y(i+1)| = 1 作为 Lemma 去证明：
gcd(x(i),x(i+1)) = gcd(y(i),y(i+1)) 同时 = 1 的！再次谢谢大大的启蒙。
这个表达方式只要 column vector 加上递回式的数学归纳法即可，用不到矩阵运算
那麽高级的定理。
※ 编辑: alan23273850 (140.109.20.138 台湾), 05/11/2021 23:48:58
23F：→ LPH66 : 这个做法就是我描述的矩阵法脱去矩阵型式的描述 05/12 00:11
24F：→ LPH66 : 这个 Lemma 等同於「系数矩阵的行列式为正负 1」 05/12 00:12
25F：→ alan23273850: 对的！真的再次感谢大大！ 05/12 02:05