——!x^n+y^n=z^n
最大公约数（gcd）及其算法（欧几里得算法）
对于正整数 a，b 若存在c使得c|a且c|b，则称c为a，b的公约数，若c还满足a=pc，b=qc，且p，q互质，则称c为a，b的最大公约数，记为（a，b）。
当然我们可以用枚举的方法求gcd，但还有一种算法可以高效解决这一问题，叫做欧几里得算法...这里主要给出一种证明...
欧几里得算法：（a，b）=（a，b%a）[不妨设a<=b]
``````
证明：
设（a，b）=c；
则a=pc，b=qc，且（p，q）=1；
由带余除法可知，b=am+r，0=<r<a；
∵a=pc，b=qc
∴r=c（q-mp）
这表明c是r的约数，故c|（a，b%a）；
若c≠（a，b%a） 记c'=（a，b%a），c'>c；
即r=c（q-mp）=b-am=c'r'
a=c'a'
=>b=c'r'+c'a'm 这表明c'|a，c'|b，然而c'>c 这与c是（a，b）矛盾
固原命题得证。
``````
身为lowbee的我乱写一通代码：
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
裴蜀定理与扩展欧几里得：
裴蜀定理：ax+by=c <=> (a,b)|c <=> ax+by=(a,b)有解
特别地，ax+by=1 <=> (a,b)=1 （其实证明这个就能得到一般的裴蜀定理）
``````
简单说明一下，记住就好把，别太纠结：
若(a,b)=1,则b不整除 a，2a，L，（b-1）a；（这个操作比较显然...）···①
下证上面的式子除以b两两不同：
若存在ka≡ ma（mod b），那么b|a（k-m）[不妨设k>m，且k，m∈[1,(b-1)]∩N]
这与①产生矛盾，故命题成立。
故一定存在0<k<b使得 ka≡1（mod b），即存在 ax+by=1。
``````
那么问题来了，怎么求解x，y？
若x=x0,y=y0是方程的一组解，且（a，b）=1，我们容易得到她的所有解：
a（x0+tb）+b（y0-ta）=1 （t∈Z）。
所以我们只要求得一组解就行了。当然这个问题不好想，如果a|b，那就十分显然了
a*1+b*0=a（gcd（a，b））[特殊情况的话a=1]，这时候能想到什么？
欧几里得算法！
我们先假设 ax0+by0=1（a>b），我们考虑b，a%b的情况，由裴蜀定理我们易知：
存在 bx1+（a%b）y1=1=ax0+by0成立，如果我们在运用编程的特性，我们可以知道：
a%b=a-[a/b]*b，这意味着我们可以对上式进行变形（这种操作就自己画画把…）
得到：
x0=y1；y0=x1-[a/b]y1；
这不就是很好的递归操作吗？其实这就是上面这个操作就是扩展欧几里得算法。
接下来是蒟蒻的渣代码：
int x,y;
void egcd(int a,int b){
if(b==0){
x=1;
y=0;
return ;
}
int p,q;
egcd(b,a%b);
p=y;
q=x-(a/b)*y;
x=p;
y=q;
return ;
}
可以去做同余方程加深理解（luogu的...）：https://www.luogu.org/problem/show?pid=1082#sub
2017-07-21