【車部-輾轉相除法】
<div align="center"><font size="5"><b>【<font color="Red">車部-輾轉相除法</font>】</b><br></font></div><b><br>第1945頁<br><br>【輾轉相除法】ㄓㄢˇ ㄓㄨㄢˇ ㄒㄧㄤ ㄔㄨˊ ㄈㄚˇ<br><br>求兩個正整數最大公約數的算法。<br><br>以123與42為例，則以123除以42得餘數為39，再以39除42得餘數為3，再以39除42得餘數為3，再以3除39為整數。<br><br>故3為123及42的最大公約數。<br><br>對於單元多項式f(x)與g(x)，欲求其最高公因式HCF也可用此法，以次數較小者去除次數較大者，餘式之次數漸次下降，故必可得HCF。<br><br>此方法又稱為‘歐’氏（‘歐幾里得’）算則（Euclidean algorithm），係極有效之工具。<br><br>其原理為：若A=QB+R，則（A，B）=（B，R）。</b><p></p>
頁:
[1]