裴蜀定理：
对任何 a,b∈Z 和它们的最大公约数 d ，关于未知数
x
ax+by=c
推论：
a,b 互质的充要条件是存在整数 x,y 使 ax+by=1
对于 (a,b∈Z) ， ax+by=gcd(a,b) 一定有整数解 x,y 的证明：
设 d=gcd(a,b) ，可得 d∣a ， d∣b ，且 d∣(ax+by) 。
设 s 是
a
x,y∈Z
设 q=⌊a/s⌋ ，则有 r=amods=a−qs=a−q(ax+by)=a(1−qx)+b(−qy) ，因此 r 也是
a
s
a
d≥s
gcd(a,b)
a
ax+by=gcd(a,b)
对于 (a,b∈Z) ， ax+by=c 有整数解的条件是 gcd(a,b)∣c 的证明：
充分性：设 d=gcd(a,b) ，已知 ax+by=d 一定有整数解，设其解为 (x0,y0) 。 d∣c ，则存在 k∈Z ，使得 c=kd=k(ax+by)=a(kx)+b(ky) ，即解为 (kx0,ky0) 。
必要性：因 ax1+by1=c，x1,y1∈Z ，设 d=gcd(a,b) ，有 d∣a ， d∣b ， d∣(ax1,by1) ，即 d∣c
以上是本人学习过程中的一些总结，参考了算法导论，若有错误欢迎指正
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212605.html原文链接：https://javaforall.net
