最大公约数(gcd):Euclid算法证明

系统管理员 2021-12-04 05:43 268阅读 0赞

### 1个常识： ###

如果 a≥b 并且 b≤a，那么 a=b.

### 2个前提： ###

1）只在非负整数范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N.

2）0可以被任何数整除，但是0不能整除任何数，即 ∀x(x|0) and ∀x(0|x).

### 1个引理： ###

假设 k|a, k|b，则对任意的 x,y ∈ Z， k|(xa+yb)均成立.

证明：

k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)

于是有 xa+yb=xpk+yqk=(xp+yq)k

因为 k|(xp+yq)k, 所以 k|(xa+yb)

### gcd的Euclid算法证明： ###

命题：对任意 m, n ∈ N，证明gcd(m,n) = gcd(n, m mod n)

证明：

令 k=gcd(m,n),则 k|m 并且 k|n;

令 j=gcd(n, m mod n), 则j|n 并且 j|(m mod n);

对于m, 可以用n 表示为 m=pn+(m mod n);

由引理可知 j|m（其中 x=p,y=1）, 又 j|n，于是 j 是 m 和 n 的公约数（但不一定是最大的）;

因为 k 是 m 和 n 的最大公约数，所以必有 k≥j;

通过另一种表示形式：(m mod n)=m-pn,同理可得：

k|(m mod n),又k|n，于是 k 是 (m mod n) 和 n 的公约数（也不一定是最大的）;

同样由 j 是 n 和 (m mod n) 的最大公约数可以得到 j≥k;

由常识，得出结论 k=j,

即gcd(m,n) = gcd(n, m mod n) ，得证。

源 [http://www.cnblogs.com/ider/archive/2010/11/16/gcd\_euclid.html][http_www.cnblogs.com_ider_archive_2010_11_16_gcd_euclid.html]

转载于:https://www.cnblogs.com/quincy-qiu/p/4014347.html

[http_www.cnblogs.com_ider_archive_2010_11_16_gcd_euclid.html]: http://www.cnblogs.com/ider/archive/2010/11/16/gcd_euclid.html

发表评论取消回复

表情：

评论列表（有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读

相关面试中算法(最大公约数）

面试中算法(最大公约数）

约定不等于承诺〃/ 2024年05月28日 10:21/ 0 赞/ 63 阅读

相关【数论算法】最大公约数 & 最小公倍数

目录 1.概述 2.代码实现 2.1.最大公约数 2.2.最小公倍数 1.概述（1）最大公约数 (Greatest Com

分手后的思念是犯贱/ 2023年10月07日 23:28/ 0 赞/ 43 阅读

相关最大公约数算法详解

一.辗转相除法欧几里德的辗转相除法的执行过程如下： ⑴ 对于已知的两个自然数m和n，假设m>n。 ⑵ 计算m除以n，将得到的余数记为r。 ⑶

灰太狼/ 2022年09月30日 06:45/ 0 赞/ 171 阅读

相关最大公约数

什么是最大公约数 > 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（

小灰灰/ 2022年07月29日 06:26/ 0 赞/ 177 阅读

相关算法-求最大公约数

摘要：主要用到了辗转相除法（欧几里得算法），更相减损术。题目：求出两个整数的最大公约数。方法一：暴力枚举的方法，试图寻找到一个合适的整数 i，看

向右看齐/ 2022年07月15日 07:57/ 0 赞/ 216 阅读

相关最大公约数

public class GCD { //方法一 public static void gcd1(int a, int b) {

左手的ㄟ右手/ 2022年05月26日 01:28/ 0 赞/ 144 阅读

相关最大公约数

问题D：最大公约数时间限制：1秒内存限制：64 MB 提交：554解决：274 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \[

末蓝、/ 2022年05月22日 12:20/ 0 赞/ 201 阅读

相关算法-最大公约数

最大公约数是一个很经典的数学问题，对于这个问题有四种通用的解法，质因数分解法，短除法，不过比较常用的还是辗转相除法，算法出自于欧几里的著作《几何原本》，还有一个就是出自《九章算

爱被打了一巴掌/ 2022年03月31日 17:12/ 0 赞/ 248 阅读

相关最大公约数(gcd):Euclid算法证明

1个常识：如果 a≥b 并且 b≤a，那么 a=b. 2个前提： 1）只在非负整数范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N. 2）0可

系统管理员/ 2021年12月04日 05:43/ 0 赞/ 269 阅读

相关 Python - 最大公约数算法

Python 3.6 最大公约数，最大公因子 Greatest Common Divisor 辗转相除法 d

拼搏现实的明天。/ 2021年10月24日 06:48/ 0 赞/ 352 阅读