最大公因數檢視原始碼討論檢視歷史
| 最大公因數 | |
|---|---|
最大公因數，最大公約數，也稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。
基本介紹
最大公約數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)，指某幾個整數共有因子中最大的一個。
能夠整除一個整數的整數稱為其的約數（如5是10約數）；[1]
能夠被一個整數整除的整數稱為其的倍數（如10是5的倍數）；
如果一個數既是數A的約數，又是數B的約數，稱為A,B的公約數，A,B的公約數
中最大的一個（可以包括AB自身）稱為AB的最大公約數[1]
定義
如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。
例： 在2、4、6中，2就是2，4，6的最大公約數。[2] 早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高效的解法——輾轉相除法。輾轉相除法使用到的原理很聰明也很簡單，假設用f（x, y）表示x，y的最大公約數，取k = x/y，b = x%y，則x = ky + b，如果一個數能夠同時整除x和y，則必能同時整除b和y；而能夠同時整除b和y的數也必能同時整除x和y，即x和y的公約數與b和y的公約數是相同的，其最大公約數也是相同的，則有f（x, y）= f（y, x%y）（y > 0），如此便可把原問題轉化為求兩個更小數的最大公約數，直到其中一個數為0，剩下的另外一個數就是兩者最大的公約數。
例如，12和30的公約數有：1、2、3、6，其中6就是12和30的最大公約數。
輾轉相除法是古希臘求兩個正整數的最大公約數的，也叫歐幾里德算法，其方法是用較大的數除以較小的數，上面較小的除數和得出的餘數構成新的一對數，繼續做上面的除法，直到出現能夠整除的兩個數，其中較小的數（即除數）就是最大公約數。以求288和123的最大公約數為例，操作如下：
288÷123=2餘42
123÷42=2餘39
42÷39=1餘3
39÷3=13
所以3就是288和123的最大公約數。
性質
重要性質：gcd(a,b)=gcd(b,a) （交換律）
gcd(-a,b)=gcd(a,b)
gcd(a,a)=|a|
gcd(a,0)=|a|
gcd(a,1)=1
gcd(a,b)=gcd(b, a mod b)
gcd(a,b)=gcd(b, a-b)
如果有附加的一個自然數m,
則: gcd(ma,mb)=m * gcd(a,b) (分配律)
gcd(a+mb ,b)=gcd(a,b)
如果m是a和b的最大公約數，
則： gcd(a/m ,b/m)=gcd(a,b)/m
在乘法函數中有：
gcd(ab,m)=gcd(a,m) * gcd(b,m)
兩個整數的最大公約數主要有兩種尋找方法：
- 兩數各分解質因數，然後取出同樣有的質因數乘起來
- 輾轉相除法（擴展版）
和最小公倍數（lcm）的關係：
gcd(a, b) * lcm(a, b) = ab
a與b有最大公約數，
兩個整數的最大公因子可用於計算兩數的最小公倍數，或分數化簡成最簡分數。
兩個整數的最大公因子和最小公倍數中存在分配律：
- gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
- lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐標里，將點(0, 0)和(a, b)連起來，通過整數坐標的點的數目（除了(0, 0)一點之外）就是gcd(a, b)。