輾轉相除法

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

詳細算法
首先假設有兩個整數a，b，其中一個並唔等於零。

利用餘數定理，得出。

再利用餘數定理，將除，得出。

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

咁佢哋嘅公因數就係

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

因為，所以。

再推返上去，。

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

證明：

利用輾轉相除法求。所以，，。

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

證明：

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

例子 
搵13579同246810既GCD。

所以。

比舒公式
 線性商餘方程
 孫子定理

數論
演算法