二元一次方程式整數解

來證明下面的事實：

給定 ， 則二元一次方程式 有整數解的充要條件是 。

分成兩部分討論：

  •   有整數解
  •   有整數解

大綱：

一、有整數解

證明過程

  有整數解 存在 使 。

由於 且 ，根據線性組合原理， ， 即 ，得證。

線性組合原理

剛剛的證明用到線性組合的原理：

若 且 ， 則任取整數 ，都有 。

原因很直觀：

  存在整數 使   存在整數 使

故 ，的確為 的倍數。

二、 有整數解

證明會用到輾轉相除法和一些其他原理，先來看看：

餘數會整除最大公因數

將 相除的過程寫成 ，則 。

原因是根據線性組合原理，，又 ，所以 。

輾轉相除法

如果想要算最大公因數 ，根據上述原理，我們知道 相除後， 會在餘數 的因數中，所以 。 我們只要找出 即可。

現在我們把 相除，會得到新餘數 。同理我們只要找 最大公因數即可。依序做下去的話，餘數會越來越小，但這些餘數都是 的倍數，我們於是有餘數的數列：

  ，且 整除所有 。

由於餘數越來越小的的原因，最後一定會有某個 是我們要找的 。

由於 ，故 ，也就是說這兩個餘數 繼續做除法會整除，不會有新餘數了。

將最大公因數 表為

根據輾轉相除法，假設今天只做三次就找到 ：

       （整除結束， 為最小公因數）

根據第三個式子，我們注意到 可以用 的線性組合表示。 根據第二個式子， 又可以用 的線性組合表示。 根據第一個式子， 又可以用 的線性組合表示。

所以 可以用 的線性組合表示。

結論： 總可以表為 的線性組合。

開始證明第二部分

目標： 有整數解。

  代表 ， 原方程式改寫為 。

剛才說 總可以表為 的線性組合，所以總存在整數 使 。等號兩邊同乘以 得到 ，再和剛才的 比較係數，得到 ， ，得證。

Note: 可以練習真的去舉個例子，然後找找看找這種方程式的整數解。關鍵步驟是把 表為 的線性組合，利用輾轉相除法。