最大公約數・最小公倍數計算器
輸入兩個正整數後，用輾轉相除法（歐幾里得演算法）求出最大公約數（GCD），並逐步顯示計算過程。同時計算出最小公倍數（LCM）。
| 最大公約數（GCD） | |
|---|---|
| 最小公倍數（LCM） |
輾轉相除法的計算過程
| 計算式 |
|---|
| = × + |
什麼是輾轉相除法（歐幾里得演算法）
輾轉相除法是求兩個整數最大公約數的經典演算法。其步驟是："關注較大數除以較小數所得的餘數，用除數和餘數這一組數重複相同的操作，當餘數變為0時，此時的除數即為最大公約數"。即使是很大的數，也能通過較少的步驟準確求出最大公約數。這一方法記載於西元前300年左右歐幾里得所著的《幾何原本》中，被認為是現存最古老的演算法之一。
最大公因數・最小公倍數計算是什麼
最大公因數（GCD）是能共同整除兩個整數的最大整數，最小公倍數（LCM）則是兩個整數的公倍數中最小的整數。本工具只需輸入兩個正整數，便會以輾轉相除法即時算出這兩個值，並逐步顯示計算過程（被除數、除數、商、餘數）。
以手算而言，一般是從質因數分解中尋找共同因數，但數字愈大，質因數分解本身便愈費工夫。本工具採用的輾轉相除法只需重複除法即可求得最大公因數，因此位數很大的整數之間也能以相同步驟計算。輸入僅限1以上的整數，若輸入0、負數或小數則不會顯示計算結果。
最大公因數・最小公倍數計算的使用方式
- 輸入數值A 輸入欲求最大公因數、最小公倍數的第一個正整數。
- 輸入數值B 輸入另一個正整數。A與B孰大孰小、何者在先皆不影響結果。
- 確認結果 最大公因數（GCD）與最小公倍數（LCM）會自動顯示。
- 確認計算過程 輾轉相除法的各步驟（被除數＝除數×商＋餘數）會以表格顯示，可循序追蹤至餘數為0為止。
用好本工具的小技巧
- 最小公倍數（LCM）可以用"A×B÷最大公約數（GCD）"這一公式求出。常用於分數通分，或求多個週期不同的日程何時會重合。
- 如果兩個數互質（最大公約數為1），那麼最小公倍數就直接等於A×B。
- 輾轉相除法的一個實用優點是：即使是求較大數字之間的最大公約數，它也比先做質因數分解再求解要快。
- 輸入的兩個數字的大小順序不影響結果，程式內部會自動從較大的數開始計算。
最大公因數・最小公倍數計算的活用場景
分數約分的事前準備
求出分子與分母的最大公因數後，以該數同除兩者即可約分。若想連約分後的結果一併確認，附約分功能的分數計算機相當便利。
計算多個週期重疊的時點
例如每3日與每5日發生的行程，下次落在同一天是3與5的最小公倍數、即15日後。可應用於班表與活動的週期調整。
數學作業・考試準備的驗算
可連同計算過程立即驗算手算所得的最大公因數、最小公倍數是否正確。
求通分分母的準備
將分母互異的多個分數通分時，各分母的最小公倍數即為新的共同分母。
確認密碼技術的基礎知識
RSA 加密的金鑰產生等，最大公因數的計算也用於現代密碼技術的根基，作為理解其原理的第一步，確認計算過程頗有助益。
用語集
- 最大公因數（GCD）
- 指能同時整除兩個以上整數的整數（公因數）之中最大者。英文稱 Greatest Common Divisor，縮寫為 GCD。
- 最小公倍數（LCM）
- 指兩個以上整數的共同倍數（公倍數）之中最小者。英文稱 Least Common Multiple，縮寫為 LCM。
- 輾轉相除法
- 指著眼於大數除以小數所得的餘數，再以除數與餘數之組重複相同操作以求最大公因數的演算法。源自古希臘數學家歐幾里得的著作。
- 互質
- 指兩個整數的最大公因數為1。互質的兩數的最小公倍數，即單純為該兩數相乘之值。
- 質因數分解
- 指將整數分解為質數乘積的形式。最大公因數、最小公倍數也可由共同質因數的組合求得，但數字較大時以輾轉相除法較快。
- 公因數・公倍數
- 公因數指多個整數共通的因數，公倍數指多個整數共通的倍數。最大公因數、最小公倍數則分別指其中最大者與最小者。
常見問題
閒話 ― 為什麼一個2000多年前的演算法至今仍在使用
輾轉相除法記載於西元前300年左右古希臘數學家歐幾里得所著的數學著作《幾何原本》（Elements）第七卷中。它被認為是現存記錄中最古老的演算法之一，即便過去了2000多年，如今依然是電腦科學教材中最先介紹的代表性演算法之一。
這一演算法之所以能沿用至今，關鍵在於其計算效率之高。數學上已證明，輾轉相除法所需的步數大致與輸入數字的位數成正比（最壞情況出現在與斐波那契數列相關的數字組合中），因此無論數字多大，都能在現實可行的時間內求出最大公約數。
現代密碼技術（如RSA加密）在金鑰生成過程中，仍然會用到最大公約數的計算（或其擴充套件版本——擴充套件歐幾里得演算法）。古代的數學發現如今支撐著網際網路安全的基礎技術之一，這一事實生動地展示了數學的普適性。