[初等数论]欧几里得算法:最大公因数/公因式求解算法的数学证明与程序实现

对广大数学或计算机爱好者来说,找两个数的公因数向来是绕不过去的问题.本文将带大家用小学二年级的知识推出上述问题的最优算法:欧几里得算法,并展示其程序实现.以下是本文索引:

  1. 欧几里得算法
    1. 简洁的定义
    2. 快速的算法
    3. 严谨的证明
    4. 优雅的程序
  2. 斐蜀定理与更多推论
    1. 斐蜀定理
    2. 更多推论

欧几里得算法

欧几里得算法又叫辗转相除法,因最早被记载于欧几里得的《几何原本》中而得名.在我国,相同的算法则最早出现于东汉的《九章算术》中.该算法是目前已知最快的最大公因数求解算法.接下来,让我们开始深入了解该算法吧!

简洁的定义

本节内容的定义范围均为自然数系,或者用集合论的写法:math(特别注意的是,这里 math ).

明确定义范围后,让我们先来定义除法:

显而易见,除法对自然数系并不封闭.也就是说,我们将任意两个自然数相除,结果却不一定是自然数.对于相除结果仍是自然数的,比如math,我们称之为整除,用数学语言表述为:

math,若 math,则称 math 能被 math 整除,或 math 整除 math,记作:math;否则称 math 不能被 math 整除,或 math 不整除 math,记作:math

而对于不能整除的情况,我们可以将结果表示为两个自然数,这就是我们小学学的带余除法,例如math.带余除法的数学定义如下:

math,则math,使得:<br>  math,<br>上式也写作:<br>  math,<br>其中 math 称为 mathmath (math 除以 math) 的不完全商 (简称商) ,mathmathmath 的最小余数 (简称余数).

接下来我们来定义下因数、公因数和最大公因数:

math,<br>若 math,则称 mathmath 的因数,如:math 都是 math 的因数.<br>若 mathmath,则称 mathmath 的公因数,如:math 的公因数有 math.<br>math 的公因数中最大的称为 math 的最大公因数,记作:math,如:math

好了,定义到此结束,接下来让我们看看以上几个概念的基本性质吧:

math

math

math

math

以上几个性质留给读者自证.

最好的算法

准备工作完成后,让我们思考下如何计算 math

我们不妨假设 math ,此时最简单的情况是 mathmath,那么分别有 mathmath

而当 math 时,我们可以用带余除法:math,写成乘法就是 math ,我们看到此处出现了四个自然数 math,我们不妨带入些具体值看看能发现什么规律吧!

math 时,显然 math,由 math 得:math.<br>当 math 时,显然 math,由 math 得:math

容易发现 math,归纳一下就是 math

进一步观察 mathmath,可以发现 math,归纳后得:math

先假设以上归纳结论是正确的,容易发现我们已经得到了将两个较大数的最大公因数求解问题转化为两个较小数的求解问题,而这样的操作是可以链式执行的,比如:math

将上述方法归纳一下就是欧几里得算法:

要求 math,由带余除法可以得到以下 math 个算式:

math

math

math

math

math

math

math

由于每次带余除法后其余数必然减少,因此有限次操作后必然存在 math 使得 math,此时所求的 math

严谨的证明

要证欧几里得算法,先要证以下命题:

math

证明:math<br>   math<br>   math<br>   math<br>   math<br>   math<br>   math<br>math

由以上命题可得算法中的 math 个算式满足:

math

math

math

math

math

math

优雅的程序

让我们直接上伪代码吧:


input a, b

if a > b:

    exchange a, b

while r != 0:

    r = b mod a

    b = a

    a = r

output b

接下来,让我们看一个 C 语言实现吧!


#include <stdint.h>

#include <stdio.h>

uint64_t gcd(uint64_t a, uint64_t b) {

    if (a > b) {

        a = a ^ b;

        b = a ^ b;

        a = a ^ b;

    }

    loop:;

    uint64_t r = b % a;

    b = a;

    a = r;

    if (r != 0) goto loop;

    return b;

}

斐蜀定理与更多推论

本节内容仅作为补充,因此除斐蜀定理外其余推论证明留作练习.

另外,本节内容默认定义范围为整数系math,上节内容的整数系延拓是显然的,在此不再赘述,请读者自行想象。

斐蜀定理

逆向观察欧几里得算法,我们可以看出:

math

math

math

以此类推式中的每一个 math 都必然可以被 math 线性表示.

反过来,可以得到:

math

也就是说,可以用 mathmath 表示 math,进一步地,我们可以得到:

math

其中 mathmath 是由 mathmath 线性表示的,而 mathmath 都是整数,所以 mathmath 都是整数.这就是著名的斐蜀定理:

math

更多推论

以下内容请自证.

math

math

math

math

math

math

math

math

math

math

numbers·math·c
78 views
Comments
登录后评论
Sign In
·

<br>不能用真是头疼

·

数论都搞出来了是吧,来点rsa加密#doge