贝祖定理

注意：若无特殊说明，本章涉及的变量皆为正整数.

对于任意 $a,b$，$ax+by=c\eq gcd(a,b)\mid c$.

设 $gcd(a,b)=d$，则：

$$\left\{\begin{aligned} &d\mid a\\ &d\mid b \end{aligned}\right. \eq \left\{\begin{aligned} &d\mid ax\\ &d\mid by \end{aligned}\right. \eq d\mid (ax+by) \eq d\mid c$$

即 $gcd(a,b)\mid c$.