請輸入一次不定方程式 ax + by = c 的係數。下方的算式和輸入欄連動，直接修改其中的數字也能計算。變更「要求的解的範圍」，還可以只列出正整數解。
請以半形數字輸入整數（不能用小數或分數），也可以輸入負數。沒有 x 項或 y 項時，請在該係數輸入 0。
計算結果與圖表
在左邊的輸入欄填入係數 a、b、c，按下「計算」，整數解和圖形就會顯示在這裡。
這個頁面可以做什麼
- 只要輸入整數係數 \(a,\ b,\ c\)，就能求出滿足 \(ax + by = c\) 的整數數對 \(x,\ y\)（整數解）
- 當 \(c\) 不是 \(a\) 和 \(b\) 的最大公因數的倍數時，就沒有整數解。會顯示判定結果，也會說明為什麼沒有解
- 可以逐行查看輾轉相除法的除法表，以及把餘數倒推回去求特解的表
- 答案不只一組：會用 \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\)（\(t\) 為整數）的一般解，以及代入不同 \(t\) 的整數解一覽表來呈現
- 可以只列出「正整數解」或「大於或等於 0 的整數解」。像「用 50 元和 80 元兩種票券湊出剛好 1,000 元，有哪些買法？」這類問題，可以直接解出來
係數只能輸入整數（不能用小數或分數）。每個係數最多 15 位數，而且 \(a\) 和 \(b\) 不能同時為 0。
這個計算有什麼用？
找出剛好湊成某個金額或個數的組合
只用 50 元和 80 元兩種票券湊出剛好 1,000 元、只用兩種砝碼量出某個重量、只用固定長度的材料拼出剛好的長度。這類「組合固定大小的東西，剛好湊到目標」的問題，就是求 \(ax + by = c\) 的整數解。
張數和個數不能是負的，所以實際上要篩選出正整數解，才算得到答案。
分辨組合包裝「湊得出、湊不出的個數」
只有 6 個裝和 10 個裝的盒子時，能不能剛好湊出訂購的個數，取決於 \(6x + 10y = c\) 有沒有大於或等於 0 的整數解。6 和 10 的最大公因數是 2，所以奇數個的訂單怎麼組合都湊不出來。
在食品或零件的裝箱作業中，看清「湊得出的個數」，直接關係到能不能接單、該準備哪些尺寸的盒子。
用沒有刻度的容器量出需要的量
只用 5 公升和 3 公升的容器量出 4 公升，這個有名的問題對應的是 \(5x + 3y = 4\) 的整數解（\(x\)、\(y\) 是用正負號表示各個容器倒入和倒出的次數）。因為 \(\gcd(5,\ 3) = 1\)，不用實際操作，從式子就能先判定：只要有這兩個容器，以 1 公升為單位的任何量都量得出來。
在實驗或烹飪時思考「只用手邊的器材，能不能做出需要的量」，用的正是這個數學。
產生網路通訊加密（RSA）的金鑰
支撐網路銀行和網路購物的 RSA 加密，在由公鑰的值 \(e\) 產生私鑰的值 \(d\) 時，要解 \(e d + \varphi k = 1\) 這個一次不定方程式（\(\varphi\) 是每把金鑰各自決定的整數）。這裡用的，就是和這個頁面相同的擴展輾轉相除法。
即使是好幾百位數的數，用這個方法也能瞬間解出來，這正是加密能夠實用的基礎之一。
把材料剛好用完的生產計畫
生產每個用 \(a\) 公克材料的產品 A，和每個用 \(b\) 公克的產品 B，想把準備好的 \(c\) 公克材料剛好用完。這個計畫就是求 \(ax + by = c\) 大於或等於 0 的整數解。產品不能只做 0.5 個，所以答案一定要是整數。
像這樣處理「答案只能是整數的規劃問題」的領域稱為整數規劃，用在生產計畫、排班、配送規劃等方面。
公式與圖形
有整數解的條件
圖形
數學寫法
（一般的數學式）
\(c\)
\(=\)
\(\gcd(a,\ b)\)
\(\times\)
\(m\)
文字寫法
（把符號換成文字的公式）
③
\(c\)：等號右邊的常數
\(=\)
①
\(g\)：\(a\) 和 \(b\) 的最大公因數
\(\times\)
②
\(m\)：某個整數
用文字讀公式
①
\(g\)：\(a\) 和 \(b\) 的最大公因數
乘以
②
\(m\)：某個整數
所得的積，如果剛好等於
③
\(c\)：等號右邊的常數
（也就是 \(c\) 是 \(g\) 的倍數），就有整數解；而且只有這個時候才有
簡單範例
\(2x + 4y = 6\) 有整數解，但 \(2x + 4y = 5\) 連一組也沒有（兩者都是 \(\gcd(2,\ 4) = 2\)）
右邊的常數（6）
\(=\)
最大公因數（2）
\(\times\)
整數（3）
\(\gcd(2,\ 4) = 2\)
\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)
\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)
思考重點
為什麼 \(c\) 一定要是 \(g\) 的倍數呢？因為 \(a\) 和 \(b\) 都是 \(g\) 的倍數，可以寫成 \(a = g a'\)、\(b = g b'\)。於是左邊變成
\(ax + by = g(a'x + b'y)\)
只要 \(x\) 和 \(y\) 是整數，左邊就一定是 \(g\) 的倍數。所以如果右邊的 \(c\) 不是 \(g\) 的倍數，不管代入什麼整數，等式都不會成立。
反過來說，只要 \(c\) 是 \(g\) 的倍數，就一定有解（保證這件事的，就是下一個公式貝祖等式）。從圖形來看，差別就在於直線 \(ax + by = c\) 會通過格子點（\(x\) 坐標和 \(y\) 坐標都是整數的點），還是從格子點之間的縫隙穿過去。
貝祖等式（用輾轉相除法找到的一組整數）
數學寫法
（一般的數學式）
\(a x_1\)
\(+\)
\(b y_1\)
\(=\)
\(\gcd(a,\ b)\)
文字寫法
（把符號換成文字的公式）
①
\(a x_1\)：\(x\) 的係數 \(a\) 乘以用輾轉相除法找到的整數 \(x_1\)
\(+\)
②
\(b y_1\)：\(y\) 的係數 \(b\) 乘以用輾轉相除法找到的整數 \(y_1\)
\(=\)
③
\(g\)：\(a\) 和 \(b\) 的最大公因數
用文字讀公式
①
\(a x_1\)：\(x\) 的係數 \(a\) 乘以用輾轉相除法找到的整數 \(x_1\)
加上
②
\(b y_1\)：\(y\) 的係數 \(b\) 乘以用輾轉相除法找到的整數 \(y_1\)
，可以剛好等於
③
\(g\)：\(a\) 和 \(b\) 的最大公因數
。這樣的整數 \(x_1,\ y_1\) 一定存在，只要把輾轉相除法倒推回去就能找到
簡單範例
對 \(7\) 和 \(5\) 做輾轉相除法，再把餘數倒推回去（\(\gcd(7,\ 5) = 1\)）
\(7\) 乘以整數 \(-2\)
\(+\)
\(5\) 乘以整數 \(3\)
\(=\)
最大公因數（1）
\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)
\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)
\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)
思考重點
輾轉相除法中的餘數，隨時都能寫成「原來兩數的整數倍之和」。實際上 \(2 = 7 - 5\)，把它代入下一步 \(1 = 5 - 2 \times 2\) 的 \(2\)，\(1\) 就變成 \(7\) 和 \(5\) 的整數倍之和。對任何兩個數都能機械式地完成這個步驟的方法，就是擴展輾轉相除法。
找到的 \(x_1,\ y_1\) 是湊出最大公因數 \(g\) 的一對整數，還不是等號右邊為 \(c\) 的解。把兩邊同乘以 \(\dfrac{c}{g}\)，就得到想要的方程式的一組解。
\(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\)
例如 \(7x + 5y = 3\)，把上面的式子乘以 3，得到 \(7 \times (-6) + 5 \times 9 = 3\)，也就是 \((x_0,\ y_0) = (-6,\ 9)\) 是一組解。這個計算機會把這樣得到的解平移到比較好看的大小再顯示（不論選哪一組當起點，下一個公式的一般解表示的都是同一群解）。
所有整數解（一般解）
圖形
數學寫法
（一般的數學式）
\(x\)
\(=\)
\(x_0\)
\(+\)
\(\dfrac{b}{g}\)
\(t\)
\(y\)
\(=\)
\(y_0\)
\(-\)
\(\dfrac{a}{g}\)
\(t\)
文字寫法
（把符號換成文字的公式）
\(x\)：整數解
\(=\)
①
\(x_0\)：特解
\(+\)
②
\(\dfrac{b}{g}\)：\(x\) 的間隔
③
\(t\)：整數
\(y\)：整數解
\(=\)
④
\(y_0\)：特解
\(-\)
⑤
\(\dfrac{a}{g}\)：\(y\) 的間隔
\(t\)：整數
用文字讀公式
①
\(x_0\)：特解
加上
②
\(\dfrac{b}{g}\)：\(x\) 的間隔
的
③
\(t\)：整數
倍，就是整數解的 \(x\)；同時
④
\(y_0\)：特解
減去
⑤
\(\dfrac{a}{g}\)：\(y\) 的間隔
的同樣 \(t\) 倍，就是整數解的 \(y\)。\(t\) 每代入一個整數就得到另一組解，這樣就能表示所有的整數解
簡單範例
\(3x + 4y = 10\) 的一組解是 \((x_0,\ y_0) = (2,\ 1)\)，而且 \(\gcd(3,\ 4) = 1\)，所以
\(x\)：整數解
\(=\)
特解（2）
\(+\)
間隔（4）
整數 \(t\)
\(y\)：整數解
\(=\)
特解（1）
\(-\)
間隔（3）
整數 \(t\)
\(3 \times 2 + 4 \times 1 = 10\)
\(x = 2 + 4t, \quad y = 1 - 3t\)
\(t = 1 \ \Rightarrow \ (x,\ y) = (6,\ -2), \quad 3 \times 6 + 4 \times (-2) = 10\)
\(t = -1 \ \Rightarrow \ (x,\ y) = (-2,\ 4), \quad 3 \times (-2) + 4 \times 4 = 10\)
思考重點
為什麼 \(x\) 只能每次差 \(\dfrac{b}{g}\)、\(y\) 只能每次差 \(\dfrac{a}{g}\) 呢？如果 \((x,\ y)\) 和 \((x_0,\ y_0)\) 都是解，把兩個式子相減，可以得到
\(a(x - x_0) = -b(y - y_0)\)
兩邊同除以 \(g\)，得到 \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\)，而 \(\dfrac{a}{g}\) 和 \(\dfrac{b}{g}\) 互質（公因數只有 1）。
於是左邊必須是 \(\dfrac{b}{g}\) 的倍數，而 \(\dfrac{a}{g}\) 裡沒有這個因數，所以可以確定 \(x - x_0\) 是 \(\dfrac{b}{g}\) 的倍數。也就是可以寫成 \(x - x_0 = \dfrac{b}{g}t\)，\(y\) 的式子也就跟著確定了。
從圖形來看，直線 \(ax + by = c\) 上的格子點會等距離整齊排列，橫向間隔是 \(\dfrac{b}{g}\)，縱向間隔是 \(\dfrac{a}{g}\)。
篩選正整數解
圖形
數學寫法
（一般的數學式）
\(x_0\)
\(+\)
\(\dfrac{b}{g}\)
\(t\)
\(\geq 1\)
\(y_0\)
\(-\)
\(\dfrac{a}{g}\)
\(t\)
\(\geq 1\)
文字寫法
（把符號換成文字的公式）
①
\(x_0\)：特解
\(+\)
②
\(\dfrac{b}{g}\)：\(x\) 的間隔
③
\(t\)：整數
\(\geq 1\)
④
\(y_0\)：特解
\(-\)
⑤
\(\dfrac{a}{g}\)：\(y\) 的間隔
\(t\)：整數
\(\geq 1\)
用文字讀公式
①
\(x_0\)：特解
加上
②
\(\dfrac{b}{g}\)：\(x\) 的間隔
的
③
\(t\)：整數
倍所得的值（＝整數解的 \(x\)）大於或等於 1，而且
④
\(y_0\)：特解
減去
⑤
\(\dfrac{a}{g}\)：\(y\) 的間隔
的同樣 \(t\) 倍所得的值（＝整數解的 \(y\)）也大於或等於 1。求出同時滿足這兩個條件的 \(t\) 的範圍，就能知道所有的正整數解
簡單範例
只用 3 個裝和 5 個裝的包裝湊出剛好 47 個（\(3x + 5y = 47\)，\((x_0,\ y_0) = (4,\ 7)\)）時
特解（4）
\(+\)
間隔（5）
整數 \(t\)
\(\geq 1\)
特解（7）
\(-\)
間隔（3）
整數 \(t\)
\(\geq 1\)
\(3 \times 4 + 5 \times 7 = 47\)
\(4 + 5t \geq 1 \ \Leftrightarrow \ t \geq -\dfrac{3}{5} \ \Leftrightarrow \ t \geq 0\)
\(7 - 3t \geq 1 \ \Leftrightarrow \ t \leq 2\)
\(0 \leq t \leq 2 \ \Rightarrow \ (x,\ y) = (4,\ 7),\ (9,\ 4),\ (14,\ 1)\)
思考重點
求張數、個數、人數的問題，答案只能是正整數（或大於或等於 0 的整數）。把一般解代入不等式求出 \(t\) 的範圍，就能只挑出符合條件的解。重點是 \(t\) 為整數，所以即使界線是像 \(t \geq -\dfrac{3}{5}\) 這樣的分數，也能往內縮到整數（這個例子是 \(t \geq 0\)）。
如果 \(a\) 和 \(b\) 同號（例如都是正數），一個不等式給出下限、另一個給出上限，所以符合條件的解一定只有有限組。如果異號（例如 \(3x - 5y = 1\)），兩個條件會是同一個方向的限制，正整數解就有無限多組。當其中一個係數是 0 時（例如 \(0x + 5y = 10\)），不是 0 的那個未知數的值只有一個，另一個可以任意變動。確定的那個值符合條件，解就有無限多組；不符合，就連一組也沒有。
反過來，也可能沒有任何符合條件的 \(t\)。這時答案就是「沒有湊得出來的組合」。
一次不定方程式 \(ax + by = c\) 只有在 \(c\) 是 \(a\) 和 \(b\) 的最大公因數 \(g\) 的倍數時，才有整數解。有解時，把輾轉相除法倒推回去求出一組特解 \((x_0,\ y_0)\)，其餘的解就都能用 \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\)（\(t\) 為整數）來表示。
符號與用語解說
符號
| \(a,\ b\) | 乘在 \(x\) 和 \(y\) 前面的係數。表示已知的數時，習慣用字母表前面的字母 \(a,\ b,\ c\)。這個頁面中兩者都是整數。 | |
| \(c\) | 方程式等號右邊的常數，取自 constant（常數）的第一個字母。相當於「想湊出的總和」，它是不是最大公因數的倍數，決定了有沒有解。 | |
| \(x,\ y\) | 要求的未知數。用字母表後面的字母表示未知數，據說是笛卡兒推廣開來的寫法。這個頁面只把整數值當作答案。 | |
| \(\gcd(a,\ b)\) | 最大公因數 | \(a\) 和 \(b\) 的最大公因數，取自 greatest common divisor（最大的共同因數）的第一個字母。台灣的課本也常簡寫成 \((a,\ b)\)（最小公倍數則寫成 \([a,\ b]\)）。 |
| \(g\) | 把最大公因數 \(\gcd(a,\ b)\) 簡寫的符號，取自 greatest（最大）的第一個字母。像一般解中的 \(\dfrac{b}{g}\)、\(\dfrac{a}{g}\) 一樣，用來避免式子變得太長。 | |
| \(x_0,\ y_0\) | 特解，也就是最先找到的一組整數解。右下角的 0 表示「作為基準的第 0 個解」。以它為起點，表示所有的整數解。 | |
| \(x_1,\ y_1\) | 把輾轉相除法倒推回去找到的一對整數，滿足 \(a x_1 + b y_1 = g\)。乘以 \(\dfrac{c}{g}\) 倍，就是特解 \((x_0,\ y_0)\)。 | |
| \(t\) | 只要是整數都可以的變數（參數），用來把所有整數解整合成一個式子。\(t\) 每代入一個整數，就出現另一組整數解。 | |
| \(m\) | 表示「\(c\) 是 \(g\) 的幾倍」的整數。表示整數的字母常用 \(m\)、\(n\)、\(k\)，據說 \(m\) 來自 multiple（倍數）的第一個字母。能寫成 \(c = g \times m\) 時才有整數解，而且只有這個時候才有。 | |
| \(q\) | 除法的商，取自 quotient（商）的第一個字母。在輾轉相除法的表中，相當於 \(13 = 5 \times 2 + 3\) 的 \(2\)。 | |
| \(r\) | 除法的餘數，取自 remainder（餘數）的第一個字母。在輾轉相除法的表中，相當於 \(13 = 5 \times 2 + 3\) 的 \(3\)。這個餘數變成 0 時，計算就結束了。 | |
| \(\geq\) | 大於或等於 | 表示「左邊大於或等於右邊」的不等號。\(x \geq 1\) 的意思是「\(x\) 大於或等於 1」。反過來的「小於或等於」寫成 \(\leq\)。 |
用語
| 一次不定方程式 | 像 \(ax + by = c\) 這樣，有兩個未知數卻只有一個式子的一次方程式。「不定」是指解不只一個；在實數範圍內，直線上的每一個點都是解。就算只看整數解，通常也有無限多組。 |
| 丟番圖方程式 | 只把整數解當作答案的方程式的總稱，名稱來自古希臘數學家丟番圖（Diophantus）。這個頁面處理的一次不定方程式，是其中最基本的一種。 |
| 整數解 | 滿足方程式的解當中，\(x\) 和 \(y\) 都是整數的解。求張數、個數、人數等「不可能有零頭的量」的問題，只有整數解才有意義。 |
| 特解 | 無限多組整數解當中，最先找到的一組。選哪一組都可以。以它為起點，用一般解的形式表示所有的解。 |
| 一般解 | 用整數 \(t\) 把所有整數解整合成一個式子來表示。\(t\) 每代入一個整數，就能取出另一組解。 |
| 最大公因數 | 能整除 2 個以上整數中每一個數的正整數當中，最大的那一個。在一次不定方程式中，這個值同時決定了「有沒有解」和「解與解的間隔」。 |
| 輾轉相除法 | 用大的數除以小的數，再換成「除數和餘數」這一組，一再重複這個操作來求最大公因數的方法，英文叫 Euclidean algorithm。餘數變成 0 時的除數就是最大公因數。這個方法記載在西元前 3 世紀左右的著作《幾何原本》中，被稱為世界上最古老的演算法。 |
| 擴展輾轉相除法 | 把輾轉相除法的除法算式由下往上依序代入，把最大公因數表示成 \(a x_1 + b y_1\) 形式的方法（英文 extended Euclidean algorithm），用來求一次不定方程式的特解。 |
| 貝祖等式 | 一定存在滿足 \(a x_1 + b y_1 = \gcd(a,\ b)\) 的整數 \(x_1,\ y_1\)，這個定理也叫貝祖定理，名稱來自法國數學家貝祖（Bézout）。它是一次不定方程式可以解的根據。 |
| 互質 | 兩個整數的最大公因數是 1。例如 3 和 4 互質。\(\dfrac{a}{g}\) 和 \(\dfrac{b}{g}\) 一定互質，這正是「解會等距離排列」的關鍵。 |
| 倍數 | 把某個整數乘以整數所得的數。\(10\) 的倍數是 \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\)。0 和負數也算是倍數。 |
| 餘數 | 整數的除法中除不盡而剩下的數。\(13 \div 5\) 的商是 \(2\)、餘數是 \(3\)。輾轉相除法只靠這個餘數往下進行。 |
| 商 | 整數的除法中，表示「裡面有幾個除數」的整數。\(13 = 5 \times 2 + 3\) 的 \(2\) 就是商。 |
| 格子點 | 坐標平面上，\(x\) 坐標和 \(y\) 坐標都是整數的點，相當於方格紙上格線的交點。一次不定方程式的整數解，就是直線 \(ax + by = c\) 上的格子點。 |
| 參數 | 為了用一個式子表示所有的解而設的、可以自由變動的變數，這個頁面的 \(t\) 就是參數。 |
| 係數 | 寫在文字前面的數。\(3x\) 的 \(3\) 就是係數。沒有寫數字的 \(x\)，係數視為 1。 |
| 不等式 | 像 \(t \geq 0\) 這樣，表示兩個值大小關係的式子。篩選正整數解時會用到。 |
建議先了解的基礎知識
為了能「真正理解意義」地使用這個頁面的計算，這裡整理了建議事先了解的基礎知識。
遇到卡關的地方，回到這張表的內容複習是最快的捷徑。
| 整數的除法與餘數（國小三年級～國中七年級，8～13 歲） |
|
| 因數、倍數與最大公因數（國小五年級～國中七年級，10～13 歲） |
|
| 代數式與一元一次方程式（國中七年級，12～13 歲） |
|
| 二元一次方程式與它的圖形（國中七年級，12～13 歲） |
|
| 不等式（國中七年級～高一，12～16 歲） |
|
| 分數的計算（國小五年級～國中七年級，10～13 歲） |
|
用 Excel 計算的方法
把下方表格整個複製，貼到 Excel 的 A1 儲存格就能直接使用。
確認「有沒有整數解」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 等號右邊的常數 c | 1000 |
| 最大公因數 g | =GCD(B1,B2) |
| c 除以 g 的餘數 | =MOD(B3,B4) |
| 有沒有整數解 | =IF(B5=0,"有整數解","沒有整數解") |
確認「貝祖等式」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 用輾轉相除法找到的 x1 | -3 |
| 用輾轉相除法找到的 y1 | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| 最大公因數 g | =GCD(B1,B2) |
由「所有整數解（一般解）」求解的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 等號右邊的常數 c | 1000 |
| 最大公因數 g | =GCD(B1,B2) |
| 特解 x0 | 4 |
| 特解 y0 | 10 |
| 整數 t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| 驗算 a×x + b×y | =B1*B8+B2*B9 |
「篩選正整數解」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 最大公因數 g | =GCD(B1,B2) |
| 特解 x0 | 4 |
| 特解 y0 | 10 |
| t 的下限（由 x ≥ 1） | =-INT((B4-1)/(B2/B3)) |
| t 的上限（由 y ≥ 1） | =INT((B5-1)/(B1/B3)) |
| 正整數解的組數 | =MAX(0,B7-B6+1) |
貼上之後，上面幾列（係數、特解）是輸入欄，下面幾列是自動計算的結果。GCD 是求最大公因數、MOD 是求相除的餘數、INT 是捨去小數部分的函數。
第 1 個表格是 50x + 80y = 1000 的例子，最大公因數是 10，1000 除以 10 的餘數是 0，所以會顯示「有整數解」。把這裡改成 1001，就會變成「沒有整數解」。
第 2 個表格用來確認把輾轉相除法倒推回去得到的 x1 = −3、y1 = 2，是否真的滿足貝祖等式。50× (−3) + 80×2 = 10，和最大公因數一致。
第 3 個表格是從一般解取出一組解的表格。t 輸入 1，得到 x = 12、y = 5，驗算那一列會回到 1000。請把 t 改成各種整數試試看。
第 4 個表格是篩選正整數解的表格。t 的下限是 0、上限是 1，所以知道正整數解有 2 組（t = 0 和 t = 1）。這兩個式子是 a 和 b 都是正數時用的，輸入負的係數時要注意不等號的方向會改變。
第 1 個表格是 50x + 80y = 1000 的例子，最大公因數是 10，1000 除以 10 的餘數是 0，所以會顯示「有整數解」。把這裡改成 1001，就會變成「沒有整數解」。
第 2 個表格用來確認把輾轉相除法倒推回去得到的 x1 = −3、y1 = 2，是否真的滿足貝祖等式。50× (−3) + 80×2 = 10，和最大公因數一致。
第 3 個表格是從一般解取出一組解的表格。t 輸入 1，得到 x = 12、y = 5，驗算那一列會回到 1000。請把 t 改成各種整數試試看。
第 4 個表格是篩選正整數解的表格。t 的下限是 0、上限是 1，所以知道正整數解有 2 組（t = 0 和 t = 1）。這兩個式子是 a 和 b 都是正數時用的，輸入負的係數時要注意不等號的方向會改變。
用 Google 試算表計算的方法
把下方表格整個複製，貼到 Google 試算表的 A1 儲存格就能直接使用。
確認「有沒有整數解」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 等號右邊的常數 c | 1000 |
| 最大公因數 g | =GCD(B1,B2) |
| c 除以 g 的餘數 | =MOD(B3,B4) |
| 有沒有整數解 | =IF(B5=0,"有整數解","沒有整數解") |
確認「貝祖等式」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 用輾轉相除法找到的 x1 | -3 |
| 用輾轉相除法找到的 y1 | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| 最大公因數 g | =GCD(B1,B2) |
由「所有整數解（一般解）」求解的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 等號右邊的常數 c | 1000 |
| 最大公因數 g | =GCD(B1,B2) |
| 特解 x0 | 4 |
| 特解 y0 | 10 |
| 整數 t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| 驗算 a×x + b×y | =B1*B8+B2*B9 |
「篩選正整數解」的表格
| x 的係數 a | 50 |
| y 的係數 b | 80 |
| 最大公因數 g | =GCD(B1,B2) |
| 特解 x0 | 4 |
| 特解 y0 | 10 |
| t 的下限（由 x ≥ 1） | =-INT((B4-1)/(B2/B3)) |
| t 的上限（由 y ≥ 1） | =INT((B5-1)/(B1/B3)) |
| 正整數解的組數 | =MAX(0,B7-B6+1) |
和 Excel 相同的公式可以直接使用（GCD、MOD、INT、MAX、IF 的名稱和功能都一樣）。把整個表格複製後貼到 A1 儲存格，再把係數改成您自己的數值即可。
用 Python 計算的方法
from math import gcd
# ax + by = c 的係數（整數）
a, b, c = 50, 80, 1000
def extended_gcd(x, y):
# 擴展輾轉相除法：傳回 gcd，以及滿足 x*s + y*t = gcd 的 s, t
if y == 0:
return x, 1, 0
g, s, t = extended_gcd(y, x % y)
return g, t, s - (x // y) * t
g = gcd(a, b)
if c % g != 0:
print(f"{c} 不是 {g} 的倍數，所以沒有整數解")
else:
_, s, t = extended_gcd(a, b)
x0, y0 = s * (c // g), t * (c // g) # 特解（一組整數解）
step_x, step_y = b // g, a // g # x 的間隔和 y 的間隔
# 平移到 x 大於或等於 0 且最小，換成比較好看的特解
n = x0 // step_x
x0, y0 = x0 - n * step_x, y0 + n * step_y
print(f"特解：(x, y) = ({x0}, {y0})")
print(f"一般解：x = {x0} + {step_x}t, y = {y0} - {step_y}t（t 為整數）")
for k in range(-2, 3):
print(f" t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
# 只取出正整數解（x >= 1 且 y >= 1）
t_low = -((1 - x0) // -step_x)
t_high = (y0 - 1) // step_y
print("正整數解：", [(x0 + step_x * k, y0 - step_y * k)
for k in range(t_low, t_high + 1)])
只用標準函式庫的 math.gcd 和用遞迴寫的擴展輾轉相除法就能解。這個例子是 50x + 80y = 1000，執行後會顯示特解 (4, 10)、一般解 x = 4 + 8t、y = 10 − 5t，以及正整數解 [(4, 10), (12, 5)]。請改掉係數試試看（最後求正整數解的部分，是 a 和 b 都是正數時用的式子）。
用 LaTeX 等數學式語言的寫法（可直接複製）
有整數解的條件
c = gcd(a, b) × m
c = \gcd(a, b) \times m
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>c</mi>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>×</mo>
<mi>m</mi>
</mrow>
</math>
c = gcd(a, b) * m
Mod[c, GCD[a, b]] == 0
irem(c, igcd(a, b)) = 0;
mod(c, gcd(a, b)) == 0
c = gcd(a,b) × m
貝祖等式（用輾轉相除法找到的一組整數）
a·x₁ + b·y₁ = gcd(a, b)
a x_1 + b y_1 = \gcd(a, b)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
<mo>+</mo>
<mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
</mrow>
</math>
a*x_1 + b*y_1 = gcd(a, b)
ExtendedGCD[a, b]
igcdex(a, b, x1, y1);
[g, x1, y1] = gcd(a, b);
a x_1 + b y_1 = gcd(a,b)
所有整數解（一般解）
x = x₀ + (b/g)t, y = y₀ − (a/g)t
x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>,</mo><mspace width="1em"/>
<mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
</mrow>
</math>
x = x_0 + (b/g)t, y = y_0 - (a/g)t
Solve[a x + b y == c, {x, y}, Integers]
isolve(a*x + b*y = c);
S = solve(a*x + b*y == c, [x y], 'Integer', true);
x = x_0 + (b/g)t, y = y_0 - (a/g)t
篩選正整數解
x₀ + (b/g)t ≥ 1 且 y₀ − (a/g)t ≥ 1
x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
<mo>,</mo><mspace width="1em"/>
<msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
</mrow>
</math>
x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1
Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]
isolve({a*x + b*y = c, x >= 1, y >= 1});
S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);
x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1
請 ChatGPT 幫忙計算的方法
你是數學（整數的性質）計算助理。請務必實際執行 Python 程式碼來進行下面的計算，並只以執行結果的數值作為回答的依據（不要用心算或推測回答）。 請求出一次不定方程式 50x + 80y = 1000 的整數解。 請分別列出下列內容： 1. 50 和 80 的最大公因數，以及 1000 是不是它的倍數 2. 輾轉相除法的除法算式（直到餘數為 0），以及倒推回去得到的、滿足 50×x1 + 80×y1 = 最大公因數 的 x1, y1 3. 特解 (x0, y0)，以及一般解 x = x0 + (b/g)t, y = y0 − (a/g)t 4. x 和 y 都大於或等於 1 的所有整數解 請在 Python 中用 math.gcd 和擴展輾轉相除法精確計算，並列出計算所用的公式和執行結果的數值。
使用方法
-
1輸入數值在輸入欄中輸入要計算的數值
-
2計算按下「計算」按鈕
-
3查看結果計算結果會立即顯示。計算的思路和公式的解說，也都能在同一個頁面查看
DataChef 的特色
簡單又免費
免費且無使用次數限制
不需專業知識，操作直覺又簡單
不需專業知識，操作直覺又簡單
免註冊會員
開啟頁面即可立即使用
無須登錄任何個人資料
無須登錄任何個人資料
安全又安心
通訊全程高度加密
按下「下載」後自動刪除檔案
按下「下載」後自動刪除檔案
高速
顯示與轉換都快速順暢，毫無等待壓力
無浮水印
沒有浮水印
無須標註來源出處
無須標註來源出處
可商業使用
可免費用於商業用途
亦無須事先取得商用授權
亦無須事先取得商用授權
相關功能
最大公因數計算機（GCD、GCF）
計算 2 個以上整數的最大公因數，附質因數分解和輾轉相除法的解說
最小公倍數（LCM）計算機
計算 2 個以上整數的最小公倍數，也能確認它和最大公因數的關係
質因數分解計算機（短除法、標準分解式、正因數個數）
把整數分解成質數相乘的形式，也能用來確認兩數是否互質
聯立方程式計算機（附加減消去法、代入消去法過程）
用和國中課本相同的加減消去法、代入消去法步驟解二元一次聯立方程式，也能畫出兩條直線並判定無解或無限多解
