輾轉相除法例子:
輾轉相除法,或者叫歐幾里得演算法(英文:Euclidean algorithm),係求最大公因數嘅算法。輾轉相除法首次記載喺約前300年古希臘嘅歐幾里得嘅《幾何原本》入面,而中國最早記載喺東漢嘅《九章算術》。
首先假設有兩個整數a,b,其中一個並唔等於零。
利用餘數定理,得出
。
再利用餘數定理,將
除
,得出
。
重複以上步驟,直到可以餘盡為止,如果係n次搞掂嘅話,即係
,得出
。
咁佢哋嘅公因數就係
假設有兩個整數
。利用餘數定理,得知有一個
同埋
,得到
之後,利用最大公因數既性質,得知
。根據輾轉相除法,
同一個原理,
。直到
,得到
,得知
。
因為
,所以
。
再推返上去,
。
第一個應用係用嚟證明「如果
,咁就
。」
證明:
利用輾轉相除法求
。
所以,
,
。
由上面可以推斷到「任何整數
,
。」
證明:
如果
,咁
,即係
。即係要假設
,咁樣
。
搵13579同246810既GCD。
所以
。
|
---|
數論分支 | |
---|
數字概念 | |
---|
基本概念 | |
---|
基本定理 | |
---|
進階數論概念 | |
---|
進階數論理論 | |
---|
|