‘壹’ 欧几里得辗转相除法
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 另一种求两数的最大公约数的方法是更相减损法。辗转相除法是用来计算两个整数的最大公约数。假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然a = mc和b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 a和b的最大公约数，所以c也一定是r的最大公约数，因为r = mc - nck = (m-nk)c。
因此gcd(a,b) = gcd(b,r)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。
举例两个整数为1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此时余数为零，则21为两个数的最大公约数。
贝祖公式表明对于任意两个整数a和b，都可以找到一对可为负的整数x和y，可以使等式xa + yb = m，其中m为a和b的最大公约数，合理性稍加思考可得。如果m为1说明a和b互素。所以在互素的情况下，xa + yb = 1。这个等式对于求乘法逆元有很大的帮助。
那么如何通过贝祖公式及扩展欧几里得算法来求乘法逆元呢？举一个例子来描述什么是乘法逆元。如果ab mod m = 1，或者可以表示为ab ≡ 1 mod m，这里b就是a关于模数m的乘法逆元。计算乘法逆元的方法就是扩展欧几里得算法，以下通过一个例子来帮助理解：
假设我们要求3 关于模26的乘法逆元(隐含了3和26的最大公约数为1，即互素)。当a = 3，b = 26，则根据贝祖公式，存在整数x和y，3x + 26y = 1。
思路就是等号两边同时mod 26，等式则变成(3x + 26y) mod 26 = 1 mod 26，根据模运算的性质(a + b) mod m = (a mod m + b mod m) mod m。
所以展开等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化简最终得到(3x mod 26) mod 26 = 1 mod 26。我们发现3x mod 26 = 1正好符合了乘法逆元的定义，所以欧几里得算法就是解x的关键。
下面将通过辗转相除法来求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
统一将余数换到等号左边：
2 = 26 - 3 * 8
1 = 3 - 2 * 1
将第一行的2替换到第二行，保证等式左边永远为1，等式右边变成仅由3x + 26y组成。
1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26
可得x = 9
最后9就是3关于模26的乘法逆元。它可以应用于仿射加密。
附：仿射加密的公式e(x) = ax + b mod m， 其中a与m互素， b为移动距离。
仿射解密公式d(x) = a-1(x - b) mod m
‘贰’ Rust语言编程实例100题-016
题目： 给定两个正整数m=128和n=60，求其最大公约数和最小公倍数。
程序分析：
（1）最小公倍数=输入的两个数之积除于它们的最大公约数，关键是求出最大公约数；
（2）求最大公约数用辗转相除法（又名欧几里德算法）
1）证明：设c是a和b的最大公约数，记为c=gcd(a,b),a>=b,
令r=a mod b
设a=kc，b=jc，则k，j互素，否则c不是最大公约数
据上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍数，且k-mj与j互素，否则与前述k，j互素矛盾,
由此可知，b与r的最大公约数也是c，即gcd(a,b)=gcd(b,a mod b)，得证。
2）算法描述：
第一步：a ÷ b，令r为所得余数（0≤r 第二步：互换：置 a←b，b←r，并返回第一步。
输出格式： 第一行输出最大公约数，第二行输出最小公倍数。
知识点 ：循环
程序执行结果：