总结/裴蜀定理

作者: ffacs 分类: 总结 发布时间: 2019-12-31 03:42

裴蜀定理

$ax+by=m$有整数解,当且仅$m=k*gcd(a,b)$,如果有解时必定有无穷解,这就是裴蜀定理。

证明

解设$a$为0,则等式变成$by=m$,$gcd(a,b)=b$,则有解当且仅当$m$是$b$的整数倍。由于$a=0$,$x$可以取任意整数,所以有无穷解。$b$为0时同理。

以下设$a,b$都不为0

设$A={ax+by;(x,y) \in Z^2)}$,下面证明$A$中最小的正元素是$gcd(a,b)$

首先$A$中至少有$|a|,|b|$,所以$A$中存在最小正元素。设最小正元素为$d_0=ax_0+by_0$,考虑对$A$中任意一个正元素对$d_0$进行带余除法,设$p=qd_0+r,0 \leq r < d_0,q \in Z^*$,但$r=p-qd_0=ax_1+by_1-aqx_0-bqy_0=a(x_1-qx_0)+b(y_1-qy_0) \in A$,所以$r=0$,也就是说$A$中任意正元素都是$d_0$的倍数。那么$d_0|a,d_0|b$,所以$d_0$是$a,b$的公约数

同時,對於$a,b$的任一公約數$d$,都有$a=kd,b=qd,d_0=ax+by=(xk+yq) \times d$, 所以$d|d_0$,即$d_0$是$a,b$的最大公約數。

QED.

发表评论

电子邮件地址不会被公开。 必填项已用*标注