裴枢定理的一些证明

裴蜀定理：
对任何 a,b∈Z 和它们的最大公约数 d ，关于未知数x和 y 的线性不定方程（称为裴蜀等式）：ax+by=c有整数解 (x,y) 当且仅当 d∣c ，可知有无穷多解。特别地，一定存在整数 x,y ，使 ax+by=d 成立。
推论：
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与 b 的线性组合集中最小的正元素，并且对于某个x,y∈Z，有 s=ax+by ，可知 s∈Z 。
设 q=⌊a/s⌋ ，则有 r=amods=a−qs=a−q(ax+by)=a(1−qx)+b(−qy) ，因此 r 也是a与 b 的一个线性组合，已知s是这个线性集合中的最小正整数，又 0≤r<s ，可得 r=0 ，因此有 s∣a ，同理有 s∣b ，因此 s 是a与 b 的公约数，所以有d≥s。因为对于任意 x,y∈Z ，有 d∣(ax+by) ，而对于某个 x,y∈Z ，有 s=ax+by ，所以有 d∣s 。但 d∣s 且 s>0 ，可得 d≤s 。综合 d≤s 和 d≥s ，得 d=s ，故 s =

上一篇： 裴蜀定理