最大公因數英文highest common factor,簡寫H.C.F.;或者greatest common divisor,簡寫G.C.D.),又叫最大公約數,係兩個或以上嘅整數入面嘅最大嗰個因數。譬如812嘅最大公因數係4

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

定義

編輯

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

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

  1.  
  2. 如果有另一個 符合條件一,上面講嘅d需要符合 

要揾GCD,可以用輾轉相除法

性質

編輯

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

  1. 如果 成立,咁 。呢個係結合餘數定理同埋可除性嘅結果。
  2. 如果 ,咁 
  3. 如果 係一個整數,唔等於,咁 。呢個 係解絕對值
證明:

假設 ,得出 

 ,代入 ,得出 

因為 ,所以 ,再由此可以推斷出 

因為 ,所以 

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

搵公因數既方法

編輯

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

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

輾轉相除法

編輯

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

 

 

 

 

 

列出公因數

編輯

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

 

 

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

應用

編輯

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

  • 假設 係整數,咁 
  • 假設 係整數,咁 只可以係 或者 
  •  
  • 如果 ,咁 
  • 如果 ,咁 

睇埋

編輯