最大公因數

出自維基百科,自由嘅百科全書

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

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

定義[編輯]

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

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

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

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

性質[編輯]

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

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

假設,得出

,代入,得出

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

因為,所以

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

搵公因數既方法[編輯]

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

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

輾轉相除法[編輯]

內文:輾轉相除法

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

列出公因數[編輯]

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

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

應用[編輯]

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

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

睇埋[編輯]