辗转相除法

一个24×60的长方形正好被十个12×12的方格填满，其中12是24和60的最大公约数。一般地，当且仅当c是a和b的公约数时，a×b尺寸的长方形可被边长c的正方形正好填满。

算法的演示动画。最初的绿色矩形的长和宽分别是a = 1071、b = 462，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（ $252 = 21 \times 12 ； 105 = 21 \times 5$ ）；因为 $252 - 105 = 21 \times (12 - 5) = 147$ ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 $21 = 5 \times 105 + (-2) \times 252$ 。这个重要的结论叫做贝祖定理。

单词	Euclidean algorithm
释义	Euclidean algorithm 中文百科辗转相除法在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（ $252 = 21 \times 12 ； 105 = 21 \times 5$ ）；因为 $252 - 105 = 21 \times (12 - 5) = 147$ ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 $21 = 5 \times 105 + (-2) \times 252$ 。这个重要的结论叫做贝祖定理。
随便看	strychnine nitrate的意思 strychnine nitrate injection的意思 strychnine oxide的意思 Strychnine Oxide Hydrochloride的意思 strychnine oxide sulfate的意思 strychnine phenol sulfonate的意思 strychnine phenolsulfonate的意思 strychnine phosphate的意思 Strychnine poisoning的意思 strychnine rash的意思 strychnine的意思 strychnine salicylate的意思 strychnine spike的意思 strychnine sulfate的意思 Strychnine toxicity的意思 Strychninetree的意思 strychnine valerate的意思 strychninic acid的意思 strychninise的意思 strychninism的意思 strychninium的意思 strychninization的意思 strychninize的意思 strychninolic acid的意思 strychninomania的意思

Euclidean algorithm

辗转相除法