裴蜀定理
对于任意的正整数a,b,一定存在整数非零x,y,使得ax+by=(a,b)
证明:
ax+by的最小正整数一定是gcd(a,b)
首先我们可以得到,gcd(a,b)=d;,即d是a,b的约数
那么在ax+by这个式子中,因为x,y都是非零的整数,所以无论x,y取多少
ax+by这个式子的值都不会小于d,因此这个ax+by的最小值就是d
如有错误,还请大佬指出