手机

英国房地产因利率上升陷入困境房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

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

2023-07-08 14:09:36 来源：博客园

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

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

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

欧几里得算法

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

【资料图】

简洁的定义

本节内容的定义范围均为自然数系，或者用集合论的写法：\(\in \mathbb{N}\)（特别注意的是，这里 \(0 \subset \mathbb{N}\) ）．

明确定义范围后，让我们先来定义除法：

显而易见，除法对自然数系并不封闭．也就是说，我们将任意两个自然数相除，结果却不一定是自然数．对于相除结果仍是自然数的，比如\(20 \div 5 = 4\)，我们称之为整除，用数学语言表述为：

设 \(a，b \in \mathbb{N}，b \neq 0\)，若 \(\exists q \in \mathbb{N}，a = bq\)，则称 \(a\) 能被 \(b\) 整除，或 \(b\) 整除 \(a\)，记作：\(b \mid a\)；否则称 \(a\) 不能被 \(b\) 整除，或 \(b\) 不整除 \(a\)，记作：\(b \nmid a\)．

而对于不能整除的情况，我们可以将结果表示为两个自然数，这就是我们小学学的带余除法，例如\(21 \div 5 = 4 \cdots 1\)．带余除法的数学定义如下：

设 \(a，b \in \mathbb{N}，b \neq 0\)，则\(\exists! q，r \in \mathbb{N}\)，使得： \(a = bq + r，r < b\)，上式也写作： \(a \div b = q \cdots r\)，其中 \(q\) 称为 \(b\) 除 \(a\) (\(a\) 除以 \(b\)) 的不完全商 (简称商) ，\(r\) 是 \(b\) 除 \(a\) 的最小余数 (简称余数)．

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

设 \(a，b，c \in \mathbb{N}\)，若 \(b \mid a\)，则称 \(b\) 是 \(a\) 的因数，如：\(\{1，2，4\}\) 都是 \(4\) 的因数．若 \(c \mid a\) 且 \(c \mid b\)，则称 \(c\) 是 \(a，b\) 的公因数，如：\(6，4\) 的公因数有 \(\{1，2\}\)．\(a，b\) 的公因数中最大的称为 \(a，b\) 的最大公因数，记作：\(gcd(a，b)\)，如：\(gcd(4，6) = 2\)．

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

\[1 \mid a，a \mid 0，a \mid a．\\a \mid b，b \mid c \implies a \mid c．\\a \mid b，a \mid c \implies a \mid (b \pm c)． \\gcd(a，b) = gcd (b，a)．\]

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

最好的算法

准备工作完成后，让我们思考下如何计算 \(gcd(a,b)\)．

我们不妨假设 \(a < b\) ，此时最简单的情况是 \(a \mid b\) 和 \(b \mid 0\)，那么分别有 \(gcd(a，b) = a\) 和 \(gcd(0，b) = b\)．

而当 \(a \nmid b\) 时，我们可以用带余除法：\(b \div a = q \cdots r (r < a)\)，写成乘法就是 \(b = aq + r\) ，我们看到此处出现了四个自然数 \(a，b，q，r\)，我们不妨带入些具体值看看能发现什么规律吧！

当 \(a = 12，b = 20\) 时，显然 \(gcd(a，b) = gcd(12，20) = 4\)，由 \(b=aq+r\) 得：\(q=1,r=8\)．当 \(a=18，b=30\) 时，显然 \(gcd(a,b)=gcd(18,30)=6\)，由 \(b=aq+r\) 得：\(q=1,r=12\)．

容易发现 \(4 \mid 8，6\mid 12\)，归纳一下就是 \(gcd(a，b) \mid r\)．

进一步观察 \(a\) 和 \(r\)，可以发现 \(gcd(12,8)=4=gcd(12,20)，gcd(18,12)=6=gcd(18,30)\)，归纳后得：\(gcd(a,b)=gcd(a,r)\)．

先假设以上归纳结论是正确的，容易发现我们已经得到了将两个较大数的最大公因数求解问题转化为两个较小数的求解问题，而这样的操作是可以链式执行的，比如：\(gcd(18,30)=gcd(12,18)=gcd(6,12)=gcd(0,6)=6\)．

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

要求 \(gcd(a，b),0\[b=aq_1+r_1,r_1由于每次带余除法后其余数必然减少，因此有限次操作后必然存在 \(k > 0\) 使得 \(k_{r+1}>0\)，此时所求的 \(gcd(a,b)=r_k\)．

严谨的证明

要证欧几里得算法，先要证以下命题：

\[a+b \neq 0,a证明：\(设 d 是 a,b 的公因数，则：d \mid a，d \mid b\) \(\therefore d \mid aq，\) \(又 r=b-aq，\) \(\therefore d \mid r，\) \(\therefore a，b的公因数是a,r的公因数，\) \(同理：a，r的公因数是a,b的公因数，\) \(\therefore gcd(a,b)=gcd(a,r)．\)\(\blacksquare\)

由以上命题可得算法中的 \(k+1\) 个算式满足：

\[gcd(a,b)=gcd(a,r_1),\\gcd(a,r_1)=gcd(r_1,r_2),\\gcd(r_1,r_2)=gcd(r_2,r_3),\\\vdots\\gcd(r_{k-1},r_k)=gcd(r_k,r_{k+1}=0)=r_k,\\\]

\(\therefore gcd(a,b)=r_k．\)

优雅的程序

让我们直接上伪代码吧：

input a, bif a > b:    exchange a, bwhile r != 0:    r = b mod a    b = a    a = routput b

接下来，让我们看一个 C 语言实现吧！

#include #include 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;}

斐蜀定理与更多推论

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

另外，本节内容默认定义范围为整数系\(\mathbb{Z}\)，上节内容的整数系延拓是显然的，在此不再赘述，请读者自行想象。

斐蜀定理

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

\[r_{k-1}=r_kq_{k+1},\\r_{k-2}=r_{k-1}q_k+r_k=r_kq_{k+1}q_k+r_k,\\\vdots\]

以此类推式中的每一个 \(r_i\) 都必然可以被 \(r_k\) 线性表示．

反过来，可以得到：

\[r_k=r_{k-2}-r_{k-1}q_k.\]

也就是说，可以用 \(r_{k-1}\) 和 \(r_{k-2}\) 表示 \(r_k\)，进一步地，我们可以得到：

\[r_k=sa+tb.\]

其中 \(s\) 和 \(t\) 是由 \(r_i\) 和 \(q_i\) 线性表示的，而 \(r_i\) 和 \(q_i\) 都是整数，所以 \(s\) 和 \(t\) 都是整数．这就是著名的斐蜀定理：

\[\lvert a \rvert + \lvert b \rvert \neq 0 \implies \exists s, t \in \mathbb{Z},\\ gcd(a,b)=sa+tb.\]