辗转相除法与线性丢番图方程

程序设计

发布日期: 2018-09-02

0.原理：两个整数的最大公约数等于两个整数中较小的数和两数之差的最大公约数，反复应用此原理直至其中一数为零，另一个不为零的数即为最大公约数。 1.为求简明，以下只说明如何求两个非负整数a和b的最大公约数（负数的情况是简单的）。在第一步计算时（k = 0），设r−2和r−1分别等于a和b，第2步（此时k = 1）时计算r−1（即b）和r0（第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示： a = q0 b + r0 b = q1 r0 + r1 r0 = q2 r1 + r2 r1 = q3 r2 + r3 2.伪代码

function gcd（a，b） while b ≠ 0 t ← b b ← a mod b a ← t return a

3.c++版本

3.1int gcd(int m,int n) { int t; while(t) { t=m%n; m=n; n=t; } return m; }

3.2#include <iostream> #include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { int t = a % b; int temp; while (t) { a = b; b = t; t = a % b; } return b; } int main() { int a, b, temp; cin >> a >> b; if (a < b) { temp = a; a = b; b = temp; } cout << gcd(a, b) << endl; return 0; }

3.3递归版本 3.3.1伪代码 function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) 3.3.1c++版本 int gcd(int n,int m) { if(m==0) return n; else return gcd(m,n%m); } 用辗转相除法求 GCD(x,y) 时所需的步数。红点表示所需步骤较少（快），黄、绿、蓝点所需步骤依次增加（慢）。 3.4贝祖等式 3.4.1两个数a和b的最大公约数g可以表示为a和b的线性和。 3.4.2扩展欧几里得算法在辗转相除法的基础上增加两个递归等式： sk = sk−2 − qksk−1 tk = tk−2 − qktk−1 算法开始时： s−2 = 1, t−2 = 0 s−1 = 0, t−1 = 1 加上这两个递归式后，当算法终止于rN = 0，贝祖等式的整数s和t分别由sN和tN给出。 3.5 线性丢番图方程 3.5.1 方程形如 ax+by=c 可以写成关于x的同余式 $ax\equiv c{\pmod {b}}$ 令g为a和b的最大公约数，ax + _by_能够被g整除。所以，c一定能够被g整除，不然方程就无解。方程两边若同时除以 ${\tfrac {c}{g}}$ )，方程就变成了贝祖等式： $sa+tb=g$ 其中s和t可以用扩展欧几里得算法求解。[72]所以这个丢番图方程的一个解即是：

${\begin{aligned}x_{1}=s({\tfrac {c}{g}})\\y_{1}=t({\tfrac {c}{g}})\end{aligned}}$

总体而言，丢番图方程如果有解，就一定有无数个解。[73]只需要考虑两个解 (x1, y1) 和 (x2, y2)： $ax_{1}+by_{1}=c=ax_{2}+by_{2}$

或者可以写成： $a(x_{1}-x_{2})=b(y_{2}-y_{1})$ 所以相邻两个解的x之间的差是 ${\tfrac {b}{g}}$ ，y之间的差是 ${\tfrac {a}{g}}$ 。这样，所有的解都可以表示成： ${\begin{aligned}x=x_{1}-{\tfrac {bt}{g}}\\y=y_{1}+{\tfrac {at}{g}}\end{aligned}}$