最大公因數

最大公因數（英文：highest common factor，簡寫H.C.F.；或者greatest common divisor，簡寫G.C.D.），又叫最大公約數，係兩個或以上嘅整數入面嘅最大嗰個因數。譬如8同12嘅最大公因數係4。

喺數論入面，常用嘅叫法係GCD。而兩個整數a、b既最大公因數會用$\gcd(a,b)=d$或者用$(a,b)=d$嚟表達。

定義

最大公因數嚴謹嘅數學定義需要用到可除性。

假設有兩個整數a、b，其中一個係唔等於零。a、b嘅最大公因數$\gcd(a,b)$係一個整正數d，而d符合以下兩個條件：

1. $d|a,d|b$
2. 如果有另一個$d'$符合條件一，上面講嘅d需要符合$d'<d$

要揾GCD，可以用輾轉相除法。

性質

最大公因數有幾個有用嘅性質。

1. 如果$a=qb+r$成立，咁$\gcd(a,b)=\gcd(b,r)$。呢個係結合餘數定理同埋可除性嘅結果。
2. 如果$k>0$，咁$\gcd(ka,kb)=k\times \gcd(a,b)$。
3. 如果$k$係一個整數，唔等於零，咁$\gcd(ka,kb)=|k|\gcd(a,b)$。呢個$|k|$係解絕對值。

證明：

假設$\gcd(a,b)=d$，得出$d|a,d|b$。

由$d|a$，代入$a=qb+r$，得出$d|(qb+r)$。

因為$d|b$，所以$d|qb$，再由此可以推斷出$d|r$。

因為$r=a-qb$，所以$\gcd(a,b)=\gcd(b,r)$。

呢個性質可以用嚟證明輾轉相除法。而其他兩個性質係需要用到輾轉相除法嚟證明。

搵公因數既方法

搵公因數嘅方法有好多，其中一個就係輾轉相除法，不過重有幾個都係常用。

• 輾轉相除法
• 例出公因數
• 短除法

輾轉相除法

利用輾轉相除法去搵53同123嘅GCD。

$123=53\times 2+17$

$53=17\times 3+2$

$17=2\times 8+1$

$2=2\times 1+0$

$\therefore \gcd(53,123)=1$

列出公因數

列出所有公因數去搵12同8嘅GCD：

${\begin{aligned}12&=12\times 1\\&=2\times 6\\&=3\times 4\\\end{aligned}}$

${\begin{aligned}8&=8\times 1\\&=2\times 4\\\end{aligned}}$

兩個數都有嘅因數包括1、2同4，所以最大公因數係4。

應用

公因數嘅概念可以喺數學上面證明好多有用嘅性質。

• 假設$n\in \mathbb {Z}$係整數，咁$\gcd(n,n+1)=1$。
• 假設$n\in \mathbb {Z}$係整數，咁$\gcd(n,n+2)$只可以係$1$或者$2$。
• $\gcd(\gcd(a,b),b)=\gcd(a,b)$。
• 如果$k=abc+1$，咁$\gcd(k,a)=\gcd(k,b)=\gcd(k,c)=1$。
• 如果$\gcd(a,b)=d$，咁$\gcd {\bigl (}{\frac {a}{d}},{\frac {b}{d}}{\bigr )}=1$。

睇埋

• 輾轉相除法
• 相對質數
• 最小公倍數
• 比舒公式
• 歐幾理得推論