跳去內容

輾轉相除法

出自維基百科,自由嘅百科全書
(由歐幾里得算法跳轉過嚟)
輾轉相除法例子:

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

詳細算法

[編輯]

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

利用餘數定理,得出

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

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

咁佢哋嘅公因數就係

證明

[編輯]

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

因為,所以

再推返上去,

其他應用

[編輯]

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

證明:

利用輾轉相除法求所以,

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

證明:

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

例子

[編輯]

搵13579同246810既GCD

所以

睇埋

[編輯]