題解原地址單純做收藏用，若原作者要求，立刻刪除

題解：

我們其實只需要考慮形如 a ? x mod n = 1 的方程。因為，如果能解出這樣的方程， a ? x mod n = 2 、 a ? x mod n = 3 也都自動地獲解了。假如 a ? x mod n = 1 有一個解 x = 100 ，由于 100 個 a 除以 n 余 1 ，自然 200 個 a 除以 n 就余 2 ， 300 個 a 除以 n 就余 3 ，等等，等式右邊余數不為 1 的方程也都解開了。

讓我們嘗試求解 115x mod 367 = 1 。注意，由于 115 和 367 是互質的，因此方程確實有解。我們解方程的基本思路是，不斷尋找 115 的某個倍數以及 367 的某個倍數，使得它們之間的差越來越小，直到最終變為 1 。由于 367 除以 115 得 3 ，余 22 ，因而 3 個 115 只比 367 少 22 。于是， 15 個 115 就要比 5 個 367 少 110 ，從而 16 個 115 就會比 5 個 367 多 5 。好了，真正巧妙的就在這里了： 16 個 115 比 5 個 367 多 5 ，但 3 個 115 比 1 個 367 少 22 ，兩者結合起來，我們便能找到 115 的某個倍數和 367 的某個倍數，它們只相差 2 ： 16 個 115 比 5 個 367 多 5 ，說明 64 個 115 比 20 個 367 多 20 ，又考慮到 3 個 115 比 1 個 367 少 22 ，于是 67 個 115 只比 21 個 367 少 2 。現在，結合“少 2 ”和“多 5 ”兩個式子，我們就能把差距縮小到 1 了： 67 個 115 比 21 個 367 少 2 ，說明 134 個 115 比 42 個 367 少 4 ，而 16 個 115 比 5 個 367 多 5 ，于是 150 個 115 比 47 個 367 多 1 。這樣，我們就解出了一個滿足 115x mod 367 = 1 的 x ，即 x = 150 。大家會發現，在求解過程，我們相當于對 115 和 367 做了一遍輾轉相除：我們不斷給出 115 的某個倍數和 367 的某個倍數，通過輾轉對比最近的兩個結果，讓它們的差距從“少 22 ”縮小到“多 5 ”，再到“少 2 ”、“多 1 ”，其中 22, 5, 2, 1 這幾個數正是用輾轉相除法求 115 和 367 的最大公約數時將會經歷的數。因而，算法的步驟數仍然是對數級別的，即使面對上百位上千位的大數，計算機也毫無壓力。這種求解方程 a ? x mod n = b 的算法就叫做“擴展的輾轉相除法”。

注意，整個算法有時也會以“少 1 ”的形式告終。例如，用此方法求解 128x mod 367 = 1 時，最后會得出 43 個 128 比 15 個 367 少 1 。這下怎么辦呢？很簡單， 43 個 128 比 15 個 367 少 1 ，但是 367 個 128 顯然等于 128 個 367 ，對比兩個式子可知， 324 個 128 就會比 113 個 367 多 1 了，于是得到 x = 324 。

最后還有一個問題：我們最終總能到達“多 1 ”或者“少 1 ”，這正是因為一開始的兩個數是互質的。如果方程 a ? x mod n = b 當中 a 和 n 不互質，它們的最大公約數是 d > 1 ，那么在 a 和 n 之間做輾轉相除時，算到 d 就直接終止了。自然，擴展的輾轉相除也將在到達“多 1 ”或者“少 1 ”之前提前結束。那怎么辦呢？我們有一種巧妙的處理方法：以 d 為單位重新去度量 a 和 n （或者說讓 a 和 n 都除以 d ），問題就變成我們熟悉的情況了。讓我們來舉個例子吧。假如我們要解方程 24 ? x mod 42 = 30 ，為了方便后面的解釋，我們來給這個方程編造一個背景：說一盒雞蛋 24 個，那么買多少盒雞蛋，才能讓所有的雞蛋 42 個 42 個地數最后正好能余 30 個？我們發現 24 和 42 不是互質的，擴展的輾轉相除似乎就沒有用了。不過沒關系。我們找出 24 和 42 的最大公約數，發現它們的最大公約數是 6 。現在，讓 24 和 42 都來除以 6 ，分別得到 4 和 7 。由于 6 已經是 24 和 42 的公約數中最大的了，因此把 24 和 42 當中的 6 除掉后，剩下的 4 和 7 就不再有大于 1 的公約數，從而就是互質的了。好了，現在我們把題目改編一下，把每 6 個雞蛋視為一個新的單位量，比如說“ 1 把”。記住， 1 把雞蛋就是 6 個雞蛋。于是，原問題就變成了，每個盒子能裝 4 把雞蛋，那么買多少盒雞蛋，才能讓所有的雞蛋 7 把 7 把地數，最后正好會余 5 把？于是，方程就變成了 4 ? x mod 7 = 5 。由于此時 4 和 7 是互質的了，因而套用擴展的輾轉相除法，此方程一定有解。可以解出特解 x = 3 ，在它的基礎上加減 7 的整倍數，可以得到其他所有滿足要求的 x 。這就是改編之后的問題的解。但是，雖說我們對原題做了“改編”，題目內容本身卻完全沒變，連數值都沒變，只不過換了一種說法。改編后的題目里需要買 3 盒雞蛋，改編前的題目里當然也是要買 3 盒雞蛋。 x = 3 ，以及所有形如 3 + 7n 的數，也都是原方程的解。

大家或許已經看到了，我們成功地找到了 24 ? x mod 42 = 30 的解，依賴于一個巧合： 24 和 42 的最大公約數 6 ，正好也是 30 的約數。因此，改用“把”作單位重新敘述問題，正好最后的“余 30 個”變成了“余 5 把”，依舊是一個整數。如果原方程是 24 ? x mod 42 = 31 的話，我們就沒有那么走運了，問題將變成“買多少盒才能讓最后數完余 5 又 1/6 把”。這怎么可能呢？我們是整把整把地買，整把整把地數，當然余數也是整把整把的。因此，方程 24 ? x mod 42 = 31 顯然無解。

綜上所述，如果關于 x 的方程 a ? x mod n = b 當中的 a 和 n 不互質，那么求出 a 和 n 的最大公約數 d 。如果 b 恰好是 d 的整倍數，那么把方程中的 a 、 n 、 b 全都除以 d ，新的 a 和 n 就互質了，新的 b 也恰好為整數，用擴展的輾轉相除求解新方程，得到的解也就是原方程的解。但若 b 不是 d 的整倍數，則方程無解。

備注：x為a的數量，y為b的數量(x0=1,y0=0); a=115,b=367,得3余22，x1:=1*3=3,y1:=1*1=1; a=22,b=115.得5余5,x2:=3*5+1（x0）=16,y2:=1*5+0(y0)=5; a=5,b=22 z 得4余2，x3：=14*4+3(x0)=67,y3:=5*4+1(y1)=21; a=2,b=5…