[数论]裴蜀定理详解

眼瞅着就又要CSPJ+S大洗礼了，大战在即，主包最近也是~~抱佛脚~~研究上了数论
数论内容繁多，但主包认为其中最有难度的莫过于裴蜀定理
都说前人栽树，后人乘凉，那这篇保姆级详解就送给大家，祝大家在新一轮的挑战中可以不被晒死[DOGE]
好，那二话不说，给主播点上三连(虽然王码并没有哈)，让我们一起走进邪恶的裴蜀和他的蒟蒻定理————

首先先一起看看裴蜀定理的内容：
设 a,b 是不全为零的整数，对任意整数 x,y，满足 gcd(a,b)|ax+by，且存在整数 x,y, 使得 ax+by=gcd(a,b).
简单翻译一下：
给定a,b两个不可以都为0的整数，对任意整数x,y都满足：
①ax+by%a与b的最大公约数==0
②ax+by==a与b的最大公约数
怎样？看着是不是挺简洁哒，但它的证明却十分有难度。
gogogo,先分析一下较为简单的①：
已知：a,b不同时=0，a,b,x,y是整数
求证：gcd(a,b)|ax+by
思路：
我们假设a,b的最大公约数为d,则必然有a%d==0,b%d==0
则a,b都是d的倍数,可以得到a=nd,b=md(m,n≠0)
那么简单将ax+by转化为xnd+ymd，合并同类项化为(xn+ym)d
故xnd+ymd是d的倍数，ax+by亦是d的倍数
所以ax+by必然能被d整除，即d整除ax+by，gcd(a,b)整除ax+by
证明：
∵gcd(a,b)|a,gcd(a,b)|b

∴gcd(a,b)|ax,gcd(a,b)|by,其中 x,y 均为整数

∴gcd(a,b)|ax+by

对吧？第一点也没有那么复杂嘛。
但是，对于第二点————
难度飙升！~~~~啊啊啊啊
--------------------------------------------我是分割线--------------------------
由于第二点难，我们先说证明再讲思路
已知：a,b不同时=0，a,b,x,y是整数
求证：对任意整数x,y都满足：ax+by=gcd(a,b)
证明：
设r=min{ax+by}(表示ax+by可能的最小正整数)，令p=⌊a/r⌋(a/r下取整)

∵p=⌊a/r⌋

∴a=p*r+a%r,a%r=a-p*r=a-p(ax+by)

∴a%r=a-apx-bpy=a(1-px)-bpy

∴令1-px=x',-py=y',则a%r=ax'+by'

∵0≤a%r<r  (模运算的性质)

∴0≤ax'+by'<r

∵r为ax+by的最小正整数

∴ax'+by'=a%r=0

∴r|a,照上述证法同理可得r|b

∴r|gcd(a,b)

∵gcd(a,b)|ax+by,r=ax+by  (由已经证明的①得)

∴gcd(a,b)|r,r=gcd(a,b)

∴ax+by=gcd(a,b)

∴得证

思路：
我们假设ax+by有一个最小的正整数值r,而且有a/r下取整=p
然后我们就可以轻松表示a: a=p*r+a%r
把上面的等式稍稍做一下变形，得到：a%r=a-p*r
r可以用ax+by替换：a%r=a-p*(ax+by)
把上面的等式展开并且合并同类项得到： a%r=a(1-px)-bpy
显然，上面的式子是ax+by形式的：x'=1-px,y'=-py,则a%r=ax'+by'
我们考虑a%r的值，由于模运算的性质，必然有0≤a%r<r
已经知道a%r=ax'+by'，那么0≤ax'+by'<r
而r是ax+by形式的最小正整数，不能存在比它更小的相同形式的正整数，
也就是说，ax'+by'在满足上面说的取值范围时不能是正整数
那只有一种可能：ax'+by'=0
那再转化一下：a%r=0，也就是说，a可以被r整除，
好，根据以上证法，你不妨令p=b/r下取整再从头推一遍，一定可以得出：b可以被r整除
a,b都可以被r整除，则a,b的最大公约数也可以被r整除
由已经证明的第一点，gcd(a,b)整除r(ax+by)
于是，gcd(a,b)整除r(ax+by)，r(ax+by)整除gcd(a,b)，r=gcd(a,b)
r=ax+by,ax+by=gcd(a,b)无需多言，已经完成证明^^
以上就是全部证明思路，如有错漏，请各位及时指出，谢谢