2021年3月24日 星期三

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

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

關於「二元一次方程式求整數解」,
首先要知道的事是:根據「貝祖定理(Bézout's identity)」
aX+bY=M 的式子有整數解時,若且唯若M是a及b的最大公因數d的倍數。

我太久沒寫證明,怕寫出問題;其次,這不是我要講的重點。
因此,如何證明「貝祖定理」,請參考維基(註1)。


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











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


求aX+bY=M這類式子的一組整數解(X0, Y0),普遍是用輾轉相除法
舉師範大學講義上的例子(註2,因為比較簡單)
























前面的 23= 4.5 + 3....就是來自於輾轉相除法。證明的話,就是參考輾轉相除法(註2)。


若能用觀察法,"猜出"一組,那只要帶入這個通解公式,就結束了。
若觀察不出,試試移位運算。
比如百度(註3): 5x + 11 y = 1的例子:















再不行,那得回到輾轉相除法。
比如雄中講義的下面這題,以輾轉相除法比較容易找出 aX+bY=M中的 a、b。














3172*5 + 2257* -7 = 61

通解則為:
X = 5 +37 k
Y = -7 - 52 k     k是整數。


*****
雄中講義(註2)的最後一頁如下,
我認為這屬於「韓信點兵」的題型,可用中國剩餘定理(註4)解題。




















------------------------------------------------------
學生時代做過、考過好幾次輾轉相除法的證明,而今以推導不出了,能力弱到只能解題。
而在我的美好算數學的回憶中(或說想破腦袋,哈哈),輾轉相除法最好玩的地方,
不在於求最大公因數,而是藉此得出二元一次方程式的整數解。
-------------------------------------------------------
註1:貝祖定理


註2:
1. 師大講義:歐基里得輾轉相除法

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




沒有留言:

張貼留言