什麼是GCD(最大公約數)?

GCD是能整除所有給定數的最大正整數。也稱為HCF(最高公因數)。例如,GCD(12, 18) = 6,因為6是能同時整除12和18的最大數。

什麼是LCM(最小公倍數)?

LCM是能被所有給定數整除的最小正整數。例如,LCM(4, 6) = 12,因為12是能同時被4和6整除的最小數。

輾轉相除法通過反覆應用除法來求GCD:用較大數除以較小數,用較小數替換較大數,用餘數替換較小數,重複直到餘數為零。最後一個非零餘數就是GCD。例如求GCD(48, 18): 48÷18=2餘12,然後18÷12=1餘6,然後12÷6=2餘0,所以GCD=6。

GCD和LCM通過公式相關:LCM(a,b) = |a×b| / GCD(a,b)。這意味著如果你知道兩個數的GCD,就可以輕鬆計算它們的LCM,反之亦然。這個關係對任意兩個正整數都成立。

可以,可以計算三個或更多數的GCD和LCM。對於GCD,使用性質:GCD(a,b,c) = GCD(GCD(a,b),c)。對於LCM,使用:LCM(a,b,c) = LCM(LCM(a,b),c)。只需輸入用逗號分隔的多個數。

GCD有很多應用:化簡分數(分子分母除以它們的GCD)、求解丟番圖方程、在密碼學中求模逆元、判斷兩個數是否互質(GCD=1),以及在數論中基礎的輾轉相除法。

LCM用於許多實際情況:找出事件何時重合(如公車時刻表)、通分進行分數加減法、安排週期性任務、解決涉及週期現象的問題,以及在音樂中尋找節奏模式。

如果GCD(a,b) = 1,這兩個數稱為互質或相對質數。這意味著它們除了1之外沒有公因數。例如,8和15互質,因為它們唯一的公因數是1。互質數在密碼學和數論中很重要。

用質因數分解法求GCD:(1)找出每個數的質因數,(2)找出公共質因數,(3)對每個公共質因數取最低次冪,(4)將它們相乘。例如,36=2²×3²,48=2⁴×3¹,所以GCD=2²×3¹=12。

用質因數分解法求LCM:(1)找出每個數的質因數,(2)對出現在任意數中的每個質因數取最高次冪,(3)將它們相乘。例如,12=2²×3¹,18=2¹×3²,所以LCM=2²×3²=36。

可以,無論輸入數的符號如何,GCD和LCM始終是正整數。計算器使用數的絕對值。例如,GCD(-12, 18) = 6,LCM(-4, 6) = 12。

輾轉相除法的時間複雜度為O(log(min(a,b))),即使對於非常大的數也非常高效。它是數學中最古老、最高效的演算法之一,可追溯到西元前300年左右的古希臘。

化簡分數時,將分子和分母都除以它們的GCD。例如化簡24/36:GCD(24,36)=12,所以24÷12=2,36÷12=3,得到最簡分數2/3。這確保分數處於最簡形式。

可以,這個計算器使用輾轉相除法能高效處理大整數。但是,極大的數(數百位)可能受JavaScript數字精度限制。對於大多數實際用途,它對15-16位以內的數都能完美工作。

計算兩個或多個數的最大公約數(GCD)和最小公倍數(LCM)。

