辗转相除法,又称欧几里得算法、欧氏除法,它是一种计算两个数的最大公因数的方法,本质上是通过带余除法和不断降次得到的。
步骤[]
设
和
均为正整数,反复利用带余除法,在首个
时停止作除法:
- 用
除
:
,其中
;
- 用
除
:
,其中
;
- 用
除
:
,其中
;

- 用
除
:
,其中
;
- 用
除
:
。
则
。
由于余数
,因此上述过程必然只有有限步,所以是可操作的。
通过这种方法还可求出满足
的一组系数
,只需将过程一步一步反表示即可。
简化[]
如果只要求求出最大公因数,还可将上述过程简化成下面的步骤,其中每一步是依据
:

例子[]
我们通过一个例子来说明辗转相除法是如何使用的。
求
,并求出满足
的一组整数
。
;
;
;
;
;
。
则
。

于是,一组整数可以是
。
上下节[]