什麼是輾轉相除法？
輾轉相除法（又稱歐幾里得算法）是人類已知最古老的演算法之一，由希臘數學家歐幾里得於約西元前 300 年提出。它能找出兩個整數的最大公因數（GCD），也就是能同時整除這兩個數、且不留餘數的最大整數。本計算機適用於任意兩個非負整數，並會一併算出它們的最小公倍數（LCM）。
使用方式
在標示為 a 與 b 的欄位分別輸入兩個數字後送出。計算機會以最大公因數（GCD）作為主要結果，並以最小公倍數（LCM）作為附帶結果。輸入順序並不影響答案——\(\gcd(48, 36)\) 與 \(\gcd(36, 48)\) 的結果完全相同。若輸入負數，系統會取其絕對值；若其中一個數為 0，則最大公因數就是另一個數本身。
公式原理
這個演算法仰賴一個簡單的觀念：a 與 b 的任何公因數，也必定能整除它們相除後的餘數 a mod b。因此我們不斷地用餘數來取代較大的那個數：
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$並以 \(\gcd(a, 0) = a\) 作為終止條件。
每一步都會讓數字迅速縮小，因此即使是極大的數值，也只需幾次反覆運算就能得出答案。最後再以 $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$求出最小公倍數。
實際範例
求 \(\gcd(48, 36)\)：
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$
因此最大公因數為 12，最小公倍數 $$\text{LCM} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
常見問題
如果兩個數都是 0 怎麼辦？ 在本工具中，0 與 0 的最大公因數定義為 0；由於不存在任何正的公倍數，最小公倍數同樣為 0。
為什麼它比逐一列出因數還快？ 它不需要找出每一個因數，而是利用餘數這個捷徑，每一步都大幅縮小問題規模，通常達到對數時間的效率。
能處理非常大的數字嗎？ 可以。輾轉相除法即使面對位數很多的數字也相當高效，只需進行少量的取餘（modulo）運算即可。
