数论欧拉定理的运用,数论欧拉定理

本章节不以理解算法为目的，更注重于使用。

首先需要了解扩展kxdsb的算法
———找出一对（x,y），使得其能满足ax+by=gcd(a,b)这一式子。
下面给出实现此算法的代码

void gcd(int a, int b, int& d, int& x, int& y) { if(!b){ d = a; x = 1; y = 0; } else{ gcd(b, a%b, d, y, x); y -= x*(a/b); } }

通过代码我们就可以找到一组(x,y)解。

假设另外一组解为(x1,y1)，与原式联立，就可以得到a(x-x1)=b(y1-y)，两边同时除以gcd(a,b)，得到a’(x-x1)=b’(y1-y)，a’=a/gcd(a,b),b’=b/gcd(a,b)，此时a’与b’肯定互质，所以若假设(x-x1)=kb’，则易推出(y1-y)=ka’，根据式子就可以得到其他任意两组解，x1=x+kb’，y1=y-ka’，(x1=x-kb’，y1=y+ka’，两者同等)。

结论,x’=x+kb’，y’=y-ka’ （ a’=a/gcd(a,b),b’=b/gcd(a,b) )。

此时，对于ax+by+c=0求解的问题，就可以用该结论解决。
先找到ax+by=gcd(a,b)的解x1,y1,此时对于ax+by=-c。
将ax1+by1=gcd(a,b)两边同时乘以c/gcd(a,b)，即可得到解x=x1c/gcd(a,b)，y=y1c/gcd(a,b)。