輾轉相除法

輾轉相除法原理

輾轉相除法,西方叫歐幾里得算法,係求最大公因數算法。輾轉相除法首次記載喺約前300年古希臘歐幾里得嘅《幾何原本》入面,而中國最早記載喺東漢嘅《九章算術》。

詳細算法

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

利用餘數定理,得出 

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

重複以上步驟n次,直到可以餘盡為止,即係 ,得出 

由此可得, 

證明

假設有兩個整數 。利用餘數定理,得知有一個 同埋 ,得到

 
之後,利用GCD既性質,得知 。根據輾轉相除法,
 
同一個原理, 。直到 ,得到
 
,得知 

因為 ,所以 

再推返上去, 

其他應用

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

證明:

利用輾轉相除法求 

 
所以,  

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

證明:

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

 

例子

搵13579同246810既GCD

 

所以 

睇埋