定理

(ax+by=c,;xin mathbb{Z^+},;yinmathbb{Z^+}) 成立的充要条件是 (gcd(a,b)mid c)。

证明

设 (s=gcd(a,b))，显然 (smid a)，并且 (smid b)，

因为 (x,yinmathbb{Z^+})，

所以 (smid ax,;smid by)。

显然要使得之前的式子成立，则必须满足 (c) 是 (a) 和 (b) 的公约数的倍数。

又因为 (x,yinmathbb{Z^+})，

所以 (c) 必然是 (a,b) 最大公约数的倍数。

因此，证得该定理成立。