最大公因數

最大公因數，又叫最大公約數，係兩個或以上嘅整數入面嘅最大嗰個因數。譬如8同12嘅最大公因數係4。

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

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

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

如果有另一個符合條件一，上面講嘅d需要符合

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

性質 
最大公因數有幾個有用嘅性質。
 如果成立，咁。呢個係結合餘數定理同埋可除性嘅結果。
 如果，咁。
 如果係一個整數，唔等於零，咁。呢個係解絕對值。

證明：

假設，得出。

由，代入，得出。

因為，所以，再由此可以推斷出。

因為，所以。

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

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

輾轉相除法 

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

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

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

應用 
公因數嘅概念可以喺數學上面證明好多有用嘅性質。
 假設係整數，咁。
 假設係整數，咁只可以係或者。
 。
 如果，咁。
 如果，咁。

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

數論
算術