中文数学 Wiki
Advertisement

辗转相除法,又称欧几里得算法欧氏除法,它是一种计算两个数的最大公因数的方法,本质上是通过带余除法和不断降次得到的。

步骤[]

均为正整数,反复利用带余除法,在首个时停止作除法:

,其中
,其中
,其中
,其中

由于余数,因此上述过程必然只有有限步,所以是可操作的。

通过这种方法还可求出满足的一组系数,只需将过程一步一步反表示即可。

简化[]

如果只要求求出最大公因数,还可将上述过程简化成下面的步骤,其中每一步是依据

例子[]

我们通过一个例子来说明辗转相除法是如何使用的。

,并求出满足的一组整数


于是,一组整数可以是

上下节[]

Advertisement