定理
二元一次方程 \(ax+by=c\) 的有解条件是 \(\gcd(a,b) \mid c\)。
证明
设 \(s=\gcd(a,b)\)，所以 \(s\mid a\)，并且 \(s\mid b\)。
又因为 \(x,y\) 为整数，所以 \(s\mid ax,s\mid by\)。
如果要使式子成立，则 \(c\) 一定是 \(s\) 的倍数。
所以 \(s\mid c\)，\(\gcd(a,b)\mid c\)。
标签：gcd,所以,定理,mid,ax,裴蜀 From： https://www.cnblogs.com/pdpdzaa/p/17556562.html