欧几里得算法证明
【欧几里得算法证明】欧几里得算法，也叫做辗转相除法，gcd(a, b) = gcd (b, a%b)，即a和b最大公约数等于b和a%b的最大公约数。相信大家都会用，但是很多人不知道为什么，我也看了很多文章，写的都不太相同，这里我说说我自己的证明过程：
这里的证明我分为两步求证：
1.求证：a和b的公约数等于b和a%b的公约数；
2.求证：b和a%b的公约数是最大公约数。
求证1：a和b公约数等于b和a%b的公约数
为了方便大家看，我先把下面用到的变量注一下：
n：公约数m：a%bk、k'、k''：都是常数
（先不看，跟着我的思路走，过程中忘了哪个变量是干什么的再回来看一下）
这里设一个n，n是a和b的一个公约数，所以有
a/n = k' , b/n = k'' (k'和k''都是常量)--------------①
这里既然证明a和b最大公约数等于b和a%b的最大公约数，那么这里你还需要有这三个数，a和b是已知的，那么这里我们设m = a % b(m ≠ 0 ，若m=0，b一定是a和b的最大公约数)，那么
a = kb + m(k是一个常量)--------------------------②
②变形得：
m = a - kb-----------------------------------------------③
③等式两边同时除以n得：
m/n = a/n - k(b/n)-------------------------------------④
①④结合，得：
m/n = k' - kk''--------------------------------------------⑤
看⑤式中，k、k'、k''都是常数，所以m/n是一个常数，所以n也是m的约数，所以说n是a、b、m三个的公约数，那么可以得到n也是b和a%b的公约数。
看到这我们已经得出了结论一：a和b公约数等于b和a%b的公约数。
下面只需证明结论一中的公约数是他们的最大公约数即可：
求证2：公约数是最大公约数
首先，根据结论一，我们可以找出多组数据，使得他们都有一个共同的约数n
例如：(a, b)(b, a%b)(a%b, b%(a%b))...他们每组都有一个公约数n
如此一直向下，这里我们可以设（A， B）的公约数为n，每组数据都用（A， B）来更新
（每次A都变为原来的B，B变成原来的A%B）
因为A%B总是小于B，如果一直更新下去，A%B总有变成0的时候，也就是A % B = 0
设当前组合为(A，B)，且满足条件(A % B = 0)，这时我们可以得到组合(A，B)的最大公约数为B
现在我们将上面那一行数据延伸：(a, b)(b, a%b)(a%b, b%(a%b))...(kA + B, A)(A, B)
上面这一组数据都有一个公约数n，那么我们只需证明(A, B)的最大公约数与(kA + B, A)的最大公约数相等
现在已知B是(A, B)的最大公约数，又已知(kA + B, A)(A, B)有相同的约数n
我们此时假设(A, B)的这个约数n就是最大公约数B，那么只需证明B也是(kA + B, A)的最大公约数即可得出结论这里的公约数n是最大公约数。
那么也就是求证：B是(kA + B, A)的最大公约数
已知A % B = 0得：
A =k'B----------------------------------⑥
结合⑥得：
kA + B = (kk'+1)B---------------------⑦
根据⑥⑦我们可以得出(kA + B, A)的公约数为：B以及B的约数
所以(kA + B, A)的最大公约数为B
得出结论：a和b最大公约数等于b和a%b的最大公约数，也就是欧几里得算法gcd(a, b) = gcd (b, a%b)。
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法