輾轉相除法zin2 zyun2 soeng1 ceoi4 faat3,或者叫歐幾里得演算法英文Euclidean algorithm),係求最大公因數算法。輾轉相除法首次記載喺約前300年古希臘歐幾里得嘅《幾何原本》入面,而中國最早記載喺東漢嘅《九章算術》。

輾轉相除法例子:

詳細算法

編輯

首先假設有兩個整數a,b,其中一個並唔等於零。

利用餘數定理,得出 

再利用餘數定理,將  ,得出 

重複以上步驟,直到可以餘盡為止,如果係n次搞掂嘅話,即係 ,得出 

咁佢哋嘅公因數就係  

證明

編輯

假設有兩個整數 。利用餘數定理,得知有一個 同埋 ,得到 之後,利用最大公因數既性質,得知 。根據輾轉相除法, 同一個原理, 。直到 ,得到 ,得知 

因為 ,所以 

再推返上去, 

其他應用

編輯

第一個應用係用嚟證明「如果 ,咁就 。」

證明:

利用輾轉相除法求  所以,  

由上面可以推斷到「任何整數  。」

證明:

如果 ,咁 ,即係 。即係要假設 ,咁樣  

例子

編輯

搵13579同246810既GCD

 

所以 

睇埋

編輯