欧几里得算法
这篇文章主要介绍了:
- 最大公约数(GCD)与欧几里得算法;
- 平衡欧几里得算法;
- 扩展欧几里得算法。
# 1 GCD与欧几里得算法
# 1.1 整除和素数
除法定理 。其中,
称为商,
称为余。如果
,那么我们说
整除
,
是
的约数,记作
。
GCD的定义 对,
,若
,则我们成
是
和
的公约数。如果
是所有公约数中最大的,就称为最大公约数(GCD),记为
。
注:一般定义为
。
欧几里得定理 。
证明:
# 1.2 欧几里得算法的实现
# 1.3 欧几里得算法的复杂性估计
引理:。分
和
两种情况讨论即可证明。
定理 欧几里得算法复杂度上界:
证明方法是构造数列,其中:
由此。注意它是隔一个元素减半,这就到之类复杂度上界多了系数
。
# 1.4 二进制欧几里得算法
;
- 如果
都是偶数,
;
- 如果
是偶数,
是奇数,
;
- 如果
是奇数,
是偶数,
;
- 如果
都是奇数且
,
。
# 2 平衡的欧几里得算法
第1泛化除法定理 。特别地,令
,则
第1泛化欧几里得定理 。
定理 第1泛化欧几里得算法复杂度上界:
注:系数2不见了,时间复杂度在常数上有了进步。主要来源于构造的数列不再是隔一个减半,而是相邻减半:。
# 3 扩展欧几里得算法
# 3.1 Bézout等式
Bézout等式:
证:定义,我们要证明
。“
”比较简单,我们要证明“
”。
引理1:
。易证。
引理2:
。易证。由两引理知
元素的整数线性组合仍属于
。
引理3:
令
,则
。证,可以知道
。又有引理3,
。得证。
# 3.2 扩展欧几里得算法的实现
# 3.3 欧几里得算法的矩阵诠释
对于普通的欧几里得算法,给定初始,我们可以递推:
当,
。
对于扩展欧几里得算法,我们可以采用如下的递推:
当,
。