最近小腐了一下数论，巩固了一些NOIP考察的数论基本知识。
其实是这样的：
我拿着“当Gcd(p,q)=1时，最大无法表示成px+qy（x,y>=0)的数是pq-p-q”的问题去问教我们“培优班”“兴趣班”的高中数学老师，过了两周，她给我卖关子，写了下裴蜀定理，说：“这是大一的内容，你弄不懂，因为很复杂，许多知识没学过。”，我告诉她我证明过，但是裴蜀定理ax+by中的a,b只满足整数，不一定满足a,b>=0，她一脸懵逼，显然是没有注意到”(x,y>=0)”，接着我就开始和一位数学专业的瞎扯信息学。截至本博客发表前，未有答复。
在交流中我猛然意识到，很多证明虽然我看过、理解过，但是到自己讲的时候就词穷了，于是我旷了晚修来上网找证明，要么高深莫测看不懂，要么跳步百出脑补晕，很难找到适合我这种初中生（蒟蒻）的浅显易懂的证明，我把好几种学过的知识联系起来，才算懂了个大概。
在这里总结一下，也是方便那些像我一样的蒟蒻学习。
欧几里得算法：
gcd(a,b)表示a,b的最大公约数。
a mod b 表示a 除以 b 所得的余数。
我们设a>=b, 那么算法就是 gcd(a,b)=gcd(b,a mod b)
当b=0时，gcd(a,b)=a。
为了方便，a，b全部满足a,b>=0。
如果你学信息学，这是入门级的题，你只需要打一个不超过三行的递归，即可得解。
Prove：
（1）
设a,b有公约数r。
a=uk,b=vk。
a mod b
=a-(a div b)*b (a div b 指a除以b所得到的商)
=uk-(u/v)vk
=(u-(u/v)v)k
∵u>=v
∴u-(u/v)v>=0
显然a mod b有因子r。
当a=b时，a mod b=0,这个我们就特别讨论了，按照定义gcd(a,0)=a。
故当a=b时，gcd(a,b)=gcd(b,a mod b)也成立。
综上所述，*a和b的公因数一定是b和a mod b的公因数。
那么反过来是否也成立呢？
（2）
我们设b 和 a mod b 有公因子r
b=ur, a mod b=vr。
设 a=kb+a mod b
这里的k=a div b，它是整数，但是没有确定的值。
a=kb+a mod b
=kur+vr
=(ku+v)r
我们发现还是可以提一个公因式r出来。
*b和a mod b的的公因数也一定是a和b公因数。
把两个结论串起来也就是,a和b的公因数与b和a mod b的公因数完全一样。
它们你中有我，我中有你。
那么gcd（最大公因数）自然也相等。
至此证毕。
裴蜀定理:
定理：ax+by=gcd(x,y)的关于a,b的二元二次方程一定有无穷组正整数解。
裴蜀定理是扩展欧几里得算法的基础，它的证明是一个迭代过程，和扩展欧几里得算法的求解过程类似。
这里在网上看到一篇比较好的，借用一下：http://blog.sina.com.cn/s/blog_9adbe8020100zc0j.html
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：
ax + by = m
有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。
例如，12和42的最大公因子是6，则方程12x + 42y = 6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。
特别来说，方程 ax + by = 1 有解当且仅当整数a和b互素。
裴蜀等式也可以用来给最大公约数定义：d其实就是最小的可以写成ax + by形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。
证明：
(1)若b=0,则(a,b)=a.这时定理显然成立。
(2)若a,b不等于0.
∵(a,b)=(a,-b)∴不妨设a,b都大于零，a>=b,(a,b)=d
对ax+by=d，两边同时除以d，可得(a1)x+(b1)y=1，其中(a1,b1)=1。
转证(a1)x+(b1)y=1。由带余除法：
a1=(q1)b+(r1),其中0<=r1 < b1
b1=(q2)(r1)+(r2),其中0=< r2 < r1
(r1)=(q3)(r2)+(r3),其中0=< r3 < r2
.....
(rn-3)=(qn-1)(rn-2)+(rn-1)
(rn-2)=(qn)(rn-1)+(rn)
(rn-1)=(qn+1)(rn)
于是，有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,rn)=1
故
(rn-2)=(xn)(rn-1)+1
即1=(rn-2)-(xn)(rn-1)
由倒数第三个式子（rn-1）=(rn-3)-(xn-1)(rn-2)代入上式，得
1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3)
然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1),
可证得1=(a1)x+(b1)y。
推广：
以上定理可推广到n个，n≥2
如1st IMO 1959第1题：证明对任意自然数n，(21n+4)/(14n+3)为既约分数。证明：很容易看出3(14n+3)-2(21n+4)=1，由裴蜀定理，21n+4与14n+3互质，故(21n+4)/(14n+3)为既约分数。Q.E.D.
另如：5x+4y+3z可表示全部整数.因为3，4，5互质，所以5x+4y+3z可以等于1，则必定可以等于其他任意整数
扩展欧几里得算法：
算法:求方程ax+by=1(gcd(x,y)=1)的整数解。
如果不是这个形式，如ax+by=gcd(x,y) ,先化简，求出解后乘上gcd(x,y)
根据裴蜀定理，我们知道这个方程一定有解。
ax+by=1
bx’+(a mod b) y’=1
(a mod b)x”+(b mod (a mod b))y”=1
…
如此迭代，直到 ax+ by=1 这条方程a=1,b=0,
那么此时可以得出一解x=1,y=0。
ax+by=1
bx’+(a mod b) y’=1
我们如何利用x’和y’的值来求出x和y的值呢？
ax+by=bx’+(a- a div b)y’
ax+by=ay’+bx’-(a div b)by’
ax+by=ay’+b(x’-(a div b) y’)
我们扔掉什么狗屁恒等定理，直接提个公因式，使对应的相等就行了。
即x=y’ , y=x’-(a div b) y’。
公式可以不用死背，比赛时像我这样推推就行了。
到这里三个恶心的东西就结束了，我相信很少题是裸的，都需要自己观察，如果有一些好题，我会在博客上分享。
如果读者遇到了一些好题，也可以留言，一起分享。