作者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/m.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