扩展欧几里得算法是欧几里得算法的扩展。已知整数a,b,扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个可能是负数），是他们满足贝祖等式ax+by=gcd(a,b),如果a是负数，可以把问题转换成|a|（-x）+by=gcd(a,b),然后令x’=（-x). 通常谈到最大公约数时，我们都会提到非常基本的事实：给予两个整数a,b,必存在整数x,y使得ax+by=gcd(a,b). 有两个数a,b,对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。 欧几里得算法也可以用来计算模反元素； 我也不是太懂，这个还需以后好好研究一下： 求解 x，y的方法的理解 设 a>b。 1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； 2，a>b>0 时 设 ax1+ by1= gcd(a,b); bx2+ (a mod b)y2= gcd(b,a mod b); 根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b); 则:ax1+ by1= bx2+ (a mod b)y2; 即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2; 也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2); 根据恒等定理得：x1=y2; y1=x2- [a / b] *y2; 这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
由于java没有指针，所以用指针代替比较方便
package 基本算法; import java.util.Scanner; public class 扩展欧几里得算法 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int a=sc.nextInt(); int b=sc.nextInt(); Int y=new Int(); Int x=new Int(); int m=exgcd(a, b, x, y); System.out.println(m+" "+x.v+" "+y.v); } public static int exgcd(int a,int b,Int x,Int y) { if(b==0) { x.v=1; y.v=0; return a; } // 下述由于将x，y的位置进行调换，所以式子有所不同，可以用下面的方法； // int gcd=exgcd(b, a%b, y, x); // y.v-=(a/b)*x.v; int gcd=exgcd(b, a%b, x, y); int c=y.v; y.v=x.v-(a/b)*y.v; x.v=c; return gcd; } } class Int{ int v; public Int() {}; public Int(int v) { this.v=v; } }