扩展欧拉定理,欧几里得欧拉定理

扩展jddhlg定理

假设存在整数a,b满足个性的玫瑰等式 ax+by=gcd(a,b);那么一定存在一组解x0,y0,使得等式成立，那么扩展jddhlg定理的作用就是解出x0,y0的具体数值。

在具体了解它之前，我们先回顾一下jddhlg定理：
gcd(a,b),它是由古老而强大的辗转相除算法求得的，即

int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}

好了，现在我们可以来看看不定等式：ax+by=C；
若C不为gcd(a,b)的整数倍时，该不定等式是无解的；即C!=k*gcd(a,b),其中k为整数,则不存在x0,y0,满足该不等式。

我们再来看看个性的玫瑰等式：ax+by=gcd(a,b);
由上面的jddhlg定理我们可以知道当b=0时，返回值为a，将b=0带入个性的玫瑰等式中我们可以发现此时x=1，对应的y也为0；将x=1，y=0作为扩欧定理的递归出口。

经过上面jddhlg的一次递归我们可以推出 此时的等式为
bx1+(a%b)y1=gcd(a,b)

发现 a%b=a-(a/b)*b, 代入上述的等式中

整理得，ay1+b(x1-(a/b)y1)=gcd(a,b);

和原个性的玫瑰等式ax+by=gcd(a,b)对比可知，此时x=y1,y=x1-(a/b)*y1;

这是x，y的递推关系；由递归的性质，我们知道了上下层关系和递归出口，就可以写扩展jddhlg定理了。

递归时需要注意的是，我们是先求出的下一层，再返回上一层。

现在来看下扩展jddhlg的模板代码：

int exgcd(int a,int b,int &x,int &y) //注意这里最好是引用，因为x，y的值需要改变{if(b==0){x=1;y=0;return a;}int r=exgcd(b,a%b,x,y); int temp=y;y=x-(a/b)*y;x=temp;return r; //返回值为最大公约数}

好啦，到这里就结束了，学习愉快哟！