| 释义 |
輾轉相除法 zhǎn zhuǎn xiāng chú fǎ求两个正整数的最大公约数的算法。设两数为a、bb＜a，求它们最大公约数a、b的步骤如下：用b除a，得a＝bq１＋r１０≤r１＜b。若r１=０，则a，b＝b；若r１≠0，则再用r１除b，得b＝r１q２＋r２０≤r２＜r１。若r２＝０，则a，b＝r１，若r２≠0，则继续用r２除r１，……如此下去，直到能整除为止。其最后一个非零余数即为a，b。类似地，求两个多项式的最高公因式也可用此法。数学上一种求两正整数最大公约数的方法。德Euklidischer AlgorithmusS辗转相除法 |