[數論] Extended Euclidean 算法求得的係數上界

[alan23273850 (God of Computer Science)]

各位板友大家好打給賀泰軋賀，小弟最近在複習數論，剛好遇到一個以前沒學過但

很有趣的結論，它是說當 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://www.ptt.cc/bbs/Math/M.1620664017.A.FC8.html
※ 編輯: alan23273850 (123.194.139.84 臺灣), 05/11/2021 00:34:34
推 LPH66       : 可以證明過程中的 x, y 永遠互質
→ LPH66       : 那 = 0 的互質解就是給定的這一組
→ LPH66       : 咦等等, 我想一下...我似乎搞錯了一些東西
→ LPH66       : OK, 想過了沒錯, 我以為我搞錯矩陣行列了 XD
→ alan23273850: 好的！感謝ＬＰＨ大大，我來想想怎麼證明１Ｆ
→ alan23273850: 聽起來會 reduce 到 if gcd(x1,y1) = gcd(x2,y2) =1
→ alan23273850: then gcd(x1-x2*q) = gcd(y1-y2*q) = 1 for any q
推 eikcaj102   :
→ alan23273850: 欸... 結果我還是想不到怎麼證明１Ｆ
→ alan23273850: 我現在是把係數用 1 和各種 qi 的線性組合表示，每
→ alan23273850: 一輪確實都可以用輾轉相除法得到 gcd=1 的結論，但
→ alan23273850: 還沒得到一個很一般性的推法
→ alan23273850: 啊！我終於知道怎麼證了，它必須從(1,0)和(0,1)開始
→ alan23273850: 然後證明後續的tuple作完輾轉相除法的第一個步驟的
→ alan23273850: 剩餘tuple會跟前一個tuple的形式一樣，就能證明gcd
→ alan23273850: 會不變了！這個證法真的好妙，請大大收下我的膝蓋！
推 LPH66       : 差不多是這樣沒錯, 然而我會提矩陣是因為
→ LPH66       : 推移的關係式可以用矩陣表示, 使得每一步都是乘上
→ LPH66       : 一個大致上是 2x2 基本矩陣運算的矩陣
→ LPH66       : 所要的不變量則就是這個矩陣的行列式, 開始是 1
→ LPH66       : 在運算過程中它只會是正負 1, 但如果 x y 不互質
→ LPH66       : 這個整數矩陣就會有大於 1 的行列式, 矛盾
我剛剛竟然又找到更好懂的教材＆表示方式！
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
→ LPH66       : 這個做法就是我描述的矩陣法脫去矩陣型式的描述
→ LPH66       : 這個 Lemma 等同於「係數矩陣的行列式為正負 1」
→ alan23273850: 對的！真的再次感謝大大！