欧几里德算法及其简单应用

由最大公约数的几种求法入题，引出欧几里德算法，进而对欧几里德算法进行证明并简述其简单应用
1：欧几里德算法求解两个数的最大公约数
2：扩展欧几里德算法求解二元一次不定方程的通解
3：求解模线性方程

【关键词】

欧几里德算法，最大公约数，二元一次不定方程，模线性方程

简述欧几里德算法

名称：欧几里德算法又称辗转相除法
原理：gcd(a,b) = gcd(b,a mod b)
条件: a mod b 不为0
用途：计算两个正整数a，b的最大公约数

最大公约数的其他几种解法

1：质因数分解法
把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求12与18的最大公约数
12 = 2 * 2 * 3；
18 = 2 * 3 * 3；
12与18全部的公有质因数是：2,3
所以12与18的最大公约数是2 * 3 = 6；
2：短除法
短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。
例如：求12与18的最大公约数
求12,30与50的最大公约数 所以 12与18的最大公约数是2 * 3 = 6 12,30与50的最大公约数是2 * 3 * 5 = 30 3：更相减损法
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
例如：求64与18的最大公约数
因为64与18均是偶数，用2约简：得32与9
9是奇数，故将32与9辗转相减：
32 – 9 = 23
23 – 9 = 14
14 – 9 = 5
9 – 5 = 4
5 – 4 = 1
4 – 1 = 3
3 – 1 = 2
2 – 1 = 1
所以64与18的最大公约数等于1乘以开始约掉的2，既1 * 2 = 2
既64与18的最大公约数等于2

欧几里德算法的证明

结论：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明：
∵a>b 且 a mod b ≠ 0
∴a = kb + r(k ∈ N+)
r = a mod b
假设d是a，b的一个公约数
那么 d整除a
d整除b
∵r = a mod b = a – kb
∴d整除r
即d整除a mod b
即若d是a,b的一个公约数，那么d也是b， a mod b的一个公约数
即a，b的公约数跟b, a mod b 的公约数一样，从而a, b的最大公约数也就跟b， a mod b的公约数一样 gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 得证。
欧几里德算法求最大公约数的计算机程序算法描述 int gcd(int a, int b){ if(b == 0){ return a;} return gcd(b, a%b); }

扩展欧几里德算法求解线性方程

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
可以用扩展欧几里得求出gcd（a，b）=ax+by的通解，解法如下：
当 b=0，gcd（a，b）=a。此时 x=1，y=0；
当 b≠0，设 ax+ by= gcd(a,b)
设这个方程有两个解(x1,y1),(x2,y2)
则ax1 + by1 = gcd(a, b); …①
bx2 + (a%b)y2 = gcd(b, a%b) …②
记a’ = b;
b’ = a%b;
由a = a/b*b + a%b;
可得：b’ = a%b = a - a/b*b; …③
把③代入②；
得到bx + (a - a/b*b)y = gcd(b, a%b); …④
联立①，④：
又∵gcd(a, b) = gcd(b, a%b);
∴ax1 + by1 = bx2 + (a - a/b*b)y2；
整理得到：
ax1 + by1 = ay2 + b*(x2 - a/b*y2);
所以
X1 = y2;
y1 = x2 - a/b*y2;
也就是说x1, y1的值基于x2, y2，而在求解gcd（a, b）的过程中一定会有一个时候b = 0，递归终止，那么此时x2=1，y2=0，因为是通过递归求解的，所以x2, y2的值会不断返回，直到求出最开始的x, y，
至此，可以求出gcd（a，b）=ax+by的一个解（x0, y0），作为其特解
该方程的特解求出来之后其通解就满足如下表达式：
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t 扩展欧几里德算法求解线性方程通解的计算机程序算法描述 int expand_gcd(int a, int b, int &x, int &y) { /* 大前提保证： ①ax + by = gcd(a, b)一定有整数解。 ②bx + (a%b)y = gcd(b, a%b) 与①有相同解 如果b==0；那么方程就是ax=gcd(a, b) = a； 即x = 1；另取y = 0(也可以取其他值)； */ if(b == 0) { x = 1; y = 0; return a; } int gcd = expand_gcd(b, a%b, x, y); int t = x - a/b*y; // 表达式中有x，避免x改变； x = y; y = t; return gcd; //返回的是gcd(a, b); }

求解模线性方程

同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。
求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)
设 d= gcd(a,n)，假如整数 x 和 y，满足 d= ax+ ny(用扩展欧几里德得出)。如果 d| b，则方程
a * x0 + n * y0= d， 方程两边乘以 b/ d，(因为 d|b，所以能够整除)，得到 a* x0 * b / d+ n* y0* b/ d= b。
所以 x= x0* b/ d，y= y0* b/ d 为 ax+ ny= b 的一个解，所以 x= x0* b/ d 为 ax= b (mod n ) 的解。
ax≡b (mod n)的一个解为 x0= x* (b/ d ) mod n，且方程的 d 个解分别为 xi= (x0+ i* (n/ d ))mod n {i= 0… d-1}。
设ans=x*(b/d),s=n/d;
方程ax≡b (mod n)的最小整数解为：(ans%s+s)%s;
相关证明：
证明方程有一解是: x0 = x’(b/d) mod n;
由 a*x0 = a*x’(b/d) (mod n)
a*x0 = d (b/d) (mod n) (由于 ax’ = d (mod n))
= b (mod n
证明方程有d个解: xi = x0 + i*(n/d) (mod n);
由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
= (a*x0+a*i*(n/d)) (mod n)
= a * x0 (mod n) (由于 d | a)
= b
例如:
5x=4(mod3)
解得x = 2,5,8,11,14…….
由此可以发现一个规律，就是解的间隔是3.
那么这个解的间隔是怎么决定的呢？
如果可以设法找到第一个解，并且求出解之间的间隔，那么就可以求出模的线性方程的解集了.
我们设解之间的间隔为dx.
那么有
a*x = b(mod n);
a*(x+dx) = b(mod n);
两式相减，得到:
a*dx(mod n)= 0;
也就是说a*dx就是a的倍数，同时也是n的倍数，即a*dx是a 和 n的公倍数.为了求出dx,我们应该求出a 和 n的最小公倍数,此时对应的dx是最小的.
设a 和 n的最大公约数为d,那么a 和 n 的最小公倍数为(a*n)/d.
即a*dx = a*n/d;
所以dx = n/d.
因此解之间的间隔就求出来了.
因次可求出模线性方程的解

[1]求解模线性方程部分：http://blog.csdn.net/fyxz1314/article/details/38510029
[2]扩展欧几里得算法证明部分：http://baike.baidu.com/link?url=ETEab7p6IyZpWIBp37IxGpn5A30deaHPlu9SDfdZUnJCG8__lIwQoi3Xg3ifaBenZlPLR3UAhm0UtxAa2LqmWq