扩展欧几里得算法
给予二整数 a 与 b, 必存在有整数 x 与 y 使得 ax + by = gcd(a,b) 。
有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
1、算法原理
给定整数a、b，若gcd(a,b)=1。则存在c，满足ac=1 mod b，c即为a模b的乘法逆元。
利用扩展的欧几里得算法求得满足条件的c：先做辗转相除，当a、b互素时，最后一步得到的余数为1，再从1出发，对前面得到的所有除法算式进行变形，将余数用除数和被除数表示，最终便可将1表示为a与b的一种线性组合，即
从而x就是a模b的乘法逆元。因此寻找乘法逆元的过程就是求x和y的过程。
这里我们先看一下人工计算的过程：
具体实现时使用三组变量：x1，x2，x3；y1，y2，y3；t1，t2，t3。初始化时，给x1，x2，x3别赋值1、0、a，则有
1 × a + 0 × b = a
类似地，给y1，y2，y3分别赋值0、1、b，有
0 × a + 1 × b = b
接下来开始迭代，保证在每次迭代中，有
a × t1 + b × t2 = t3
成立。为此只需在每一步中为 ti 分别赋值 (i=1,2,3) ，其中q为x3除以y3的商。
当最后t3迭代至计算结果为1时，相应的 t1 就是 a模b的乘法速元，而 t2 是b模a的乘法逆元。
2、代码部分
#include <stdio.h>
int main(int argc, char *argv[])
{int temp,q,t1,t2,t3;int a,b,swap=0;int x1,x2,x3,y1,y2,y3;printf("Input two integers: ");scanf("%d",&a);scanf("%d",&b);if (a<b) { //保证a>bswap = 1;temp = a;a = b;b = temp; }x1=1; x2=0; x3=a; // 初始y1=0; y2=1; y3=b;while (y3!=0){q=x3/y3; //商t1=x1-q*y1; t2=x2-q*y2; t3=x3-q*y3;x1=y1; x2=y2; x3=y3;y1=t1; y2=t2; y3=t3;printf("\nt1,t2,t3\t%d\t%d\t%d ;",t1,t2,t3); }printf("\n");if(x3 == 1) // 这里使用x3，组后一轮循环中，x3保存了上一步中值为1的t3{if(swap==1){printf("\ninverse of %d mod %d is:%d",b,a,x2);printf("\ninverse of %d mod %d is:%d",a,b,x1); }else{printf("\ninverse of %d mod %d is:%d",a,b,x2);printf("\ninverse of %d mod %d is:%d",b,a,x1); } }else printf("no inverse");printf("\n\n\n");return 0;
}注释：
关于判断条件是 x3==1，而不是 t3==1 的问题，while循环中本质使用的是辗转相除法，对于 ti 的赋值表达式，先看t3，t3=x3-q*y3 ，q=x3/y3 ，我理解的是 t3 就是 x3除以y3的余数，加上开始时,给 x3=a，y3=b ，所以对t3的迭代可以看成对 （a,b）做辗转相除法。
再看 t1 和 t2，为了保持线性关系ax + by = gcd(a,b)，相应的x和y的值也需要变化，这就是 t1 和 t2 的作用。
