欧几里得算法

这篇文章主要介绍了:

  1. 最大公约数(GCD)与欧几里得算法;
  2. 平衡欧几里得算法;
  3. 扩展欧几里得算法。

# 1 GCD与欧几里得算法

# 1.1 整除和素数

除法定理 formula。其中,formula称为formula称为。如果formula,那么我们说formula整除formulaformulaformula的约数,记作formula

GCD的定义formulaformula,若formula,则我们成formulaformulaformula公约数。如果formula是所有公约数中最大的,就称为最大公约数(GCD),记为formula

注:formula一般定义为formula

欧几里得定理 formula

证明:

formula

# 1.2 欧几里得算法的实现

代码
测试结果
添加测试

# 1.3 欧几里得算法的复杂性估计

引理:formula。分formulaformula两种情况讨论即可证明。

定理 欧几里得算法复杂度上界

formula

证明方法是构造数列formula,其中:

formula

由此formula。注意它是隔一个元素减半,这就到之类复杂度上界多了系数formula

# 1.4 二进制欧几里得算法

  1. formula
  2. 如果formula都是偶数,formula
  3. 如果formula是偶数,formula是奇数,formula
  4. 如果formula是奇数,formula是偶数,formula
  5. 如果formula都是奇数且formulaformula

# 2 平衡的欧几里得算法

第1泛化除法定理 formula。特别地,令formula,则formula

第1泛化欧几里得定理 formula

定理 第1泛化欧几里得算法复杂度上界

formula

注:系数2不见了,时间复杂度在常数上有了进步。主要来源于构造的数列不再是隔一个减半,而是相邻减半:formula

# 3 扩展欧几里得算法

# 3.1 Bézout等式

Bézout等式

formula

证:定义formula,我们要证明formula。“formula”比较简单,我们要证明“formula”。

  1. 引理1:formula。易证。

  2. 引理2:formula。易证。由两引理知formula元素的整数线性组合仍属于formula

  3. 引理3:formula

    formula

  4. formula,则formula。证,可以知道formula。又有引理3,formula。得证。

# 3.2 扩展欧几里得算法的实现

代码
测试结果
添加测试

# 3.3 欧几里得算法的矩阵诠释

对于普通的欧几里得算法,给定初始formula,我们可以递推:

formula

formulaformula

对于扩展欧几里得算法,我们可以采用如下的递推:

formula

formulaformula

2016-2020 Ziping Sun
京ICP备 17062397号