數學＿二元一次方程式求整數解

這篇是解法(不是證法)的資料整理。

關於「二元一次方程式求整數解」，

首先要知道的事是：根據「貝祖定理(Bézout's identity)」

ａＸ＋ｂＹ＝Ｍ 的式子有整數解時，若且唯若Ｍ是ａ及ｂ的最大公因數ｄ的倍數。

我太久沒寫證明，怕寫出問題；其次，這不是我要講的重點。

因此，如何證明「貝祖定理」，請參考維基(註１)。

*****

二元一次不定方程式的整數解通解。通解如下：

答案會有無限多組解，(X0, Y0)是當中一組。

求ａＸ＋ｂＹ＝Ｍ這類式子的一組整數解(X0, Y0)，普遍是用輾轉相除法。

舉師範大學講義上的例子(註２，因為比較簡單)

前面的 23= 4．5 + 3....就是來自於輾轉相除法。證明的話，就是參考輾轉相除法(註２)。

若能用觀察法，"猜出"一組，那只要帶入這個通解公式，就結束了。

若觀察不出，試試移位運算。

比如百度(註３)： 5x + 11 y = 1的例子：

再不行，那得回到輾轉相除法。

比如雄中講義的下面這題，以輾轉相除法比較容易找出 ａＸ＋ｂＹ＝Ｍ中的 ａ、ｂ。

3172*5 + 2257* -7 = 61

通解則為：

X = 5 +37 k

Y = -7 - 52 k 　　　　k是整數。

*****

雄中講義(註２)的最後一頁如下，

我認為這屬於「韓信點兵」的題型，可用中國剩餘定理(註４)解題。

------------------------------------------------------

學生時代做過、考過好幾次輾轉相除法的證明，而今以推導不出了，能力弱到只能解題。

而在我的美好算數學的回憶中(或說想破腦袋，哈哈)，輾轉相除法最好玩的地方，

不在於求最大公因數，而是藉此得出二元一次方程式的整數解。

-------------------------------------------------------

註１：貝祖定理

註２：

1. 師大講義：歐基里得輾轉相除法

2. 雄中求整數講義：整數解問題

註３：二元一次方程式的整數解

註４：中國剩餘定理