專欄  擴張版輾轉相除法
 
輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。
 
設 除以 ，餘數為 。
若 ，則最大公因數即為 ，計算即完成。
若 ，則  的組合置換為  和 ，然後再回到最初的步驟。
 
只要重覆 到 的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。
 
舉個實例，請以輾轉相除法求出1365和77的最大公因數。
1365＝17×77＋56   （← 依1365÷77＝17餘56的計算可知）
77＝1×56＋21 （← 依77÷56＝1餘21的計算可知）
56＝2×21＋14 （← 依56÷21＝2餘14的計算可知）
21＝1×14＋   （← 依21÷14＝1餘7的計算可知）
14＝2× ＋0 （← 依14÷7＝2餘0的計算可知）
 
因此，最大公因數為7。只要依步驟計算便可確實得到結果，因此可讓人感到輾轉相除法的實用性。
 
一次不定方程式*的解之計算
 
接下來，對互質的20和17，請以輾轉相除法求最大公因數。
20＝1×17＋3（1）
17＝5×3＋2（2）
3＝1×2＋1（3）
2＝2×1＋0
 
由於直接可看出最大公因數為1，似乎並不需要使用輾轉相除法。
然而，為求出結果的算式卻具有相當大的利用價值喔！
 
*不定方程式：Diophantine equation。
 
首先，將式（1）、（2）、（3）移項，得到下列的3個式子。
（4）
＝ （5）
＝1（6）
接下來，將式（5）代入式（6）的 中，請注意3和17。
× ＝   3  （7）
接著，將式（4）代入式（7）的  3  中，請注意20和17。
6×  3 
然後，將此一連串的步驟所得的結果改寫如下。

將上式改寫為  ，而符合  的數皆為整數。這種形式的方程式就稱為一次不定方程式，可求出整數解的  和 。
 
也就是說，利用輾轉相除法的計算過程，、 時，可得一次不定方程式的整數解。此方法即為擴張版輾轉相除法，是非常具有利用價值的運算法。
 
一般而言，若設  和  為非0的整數，且  和  的最大公因數為 ，則一次不定方程式

有整數解，而且可利用擴張版輾轉相除法求出一組解。然而，一次不定方程式的解並不僅有1組。方程式的所有的整數解皆可利用任意的整數 表示如下。
 
（8）
 
以模數運算計算倒數
 
若利用式（8）中所表示的解的公式，則一次不定方程式  的所有整數解可表示如右。
（6＋17（9）
 時，解為。