輾轉相除法

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢
輾轉相除法原理

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

詳細算法[編輯]

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

利用餘數定理,得出

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

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

由此可得,

證明[編輯]

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

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

因為,所以

再推返上去,

其他應用[編輯]

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

證明:

利用輾轉相除法求

所以,

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

證明:

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

例子[編輯]

搵13579同246810既GCD

所以

睇埋[編輯]