【五術堪輿學苑】

標題: 【車部-輾轉相除法】 [打印本頁]

作者: 吳華敏 時間: 2022-10-28 06:02
標題: 【車部-輾轉相除法】

【車部-輾轉相除法】

第1945頁

【輾轉相除法】ㄓㄢˇ ㄓㄨㄢˇ ㄒㄧㄤㄔㄨˊ ㄈㄚˇ

求兩個正整數最大公約數的算法。

以123與42為例，則以123除以42得餘數為39，再以39除42得餘數為3，再以39除42得餘數為3，再以3除39為整數。

故3為123及42的最大公約數。

對於單元多項式f(x)與g(x)，欲求其最高公因式HCF也可用此法，以次數較小者去除次數較大者，餘式之次數漸次下降，故必可得HCF。

此方法又稱為‘歐’氏（‘歐幾里得’）算則（Euclidean algorithm），係極有效之工具。

其原理為：若A=QB+R，則（A，B）=（B，R）。

歡迎光臨【五術堪輿學苑】 (http://kf.wsky.ink/)