对于 $a, b, c \in \Z$ 且 $a,b \neq 0$，研究其构成的二元一次丢番图方程 (Diophantine equation)
$$ ax + by = c $$
的整数解 $x, y \in \Z$ 的性质。
【二元一次丢番图方程有解的条件】二元一次丢番图方程 $ax + by = c$ 存在整数解的充分必要条件为 ${\rm GCD} (a, b) \mid c$。
**证：**记 GCD 分解 ${\rm GCD}(a, b) = d$，$a = a_1 d$，$b = b_1d$（$a_1 \perp b_1$）。
- $\Rightarrow$：如果方程存在整数解 $x_0, y_0$，那么 $c = a x_0 + b y_0 = d(a_1 x_0 + b_1 y_0)$，因而 $d \mid c$。
- $\Leftarrow$：由于 $d \mid c$，因而存在 $s \in \Z$ 使得 $c = sd$。根据裴蜀定理，存在 $p, q \in \Z$ 使得 $d = p a + q b$（通过辗转相除法能得到 $p, q$ 的一组具体值）。因而 $c = spa + sqb$，故 $x_0 = sp$、$y_0 = sq$ 为方程的一组解。
【二元一次丢番图方程解的结构】如果二元一次丢番图方程 $ax + by = c$ 存在整数解 $x=x_0$、$y=y_0$，那么对于任意 $x, y$，它是方程的解当且仅当：
$$ \exists t \in \Z, \quad x = x_0 - b_1 t, \quad y = y_0 + a_1t $$
，其中 GCD 分解：${\rm GCD}(a, b) = d$，$a = a_1 d$，$b = b_1d$（$a_1 \perp b_1$）。
**证：**显然 $ax_0 + by_0 = c$ 成立。
- $\Leftarrow$：可以验证 $a_1d(x_0 - b_1 t) + b_1d(y_0 + a_1t) = ax_0 + by_0 = c$。
- $\Rightarrow$：设 $ax + by = c$ 成立。与 $ax_0 + by_0 = c$ 作差可以导出 $a_1(x-x_0) + b_1(y-y_0) = 0$。即 $a_1(x-x_0) = (-b_1)(y-y_0)$。根据「互质与整除关系 4.」，存在 $t \in \Z$ 使得 $x-x_0 = -tb_1$ 且 $y-y_0 = ta_1$，即 $x = x_0 - b_1t$ 和 $y = y_0 + ta_1$。
【应用题】今有鸡翁一，直钱五，鸡母一，直钱三，鸡雏三， 直钱一。凡百钱买鸡百只，问鸡翁、鸡母、鸡雏各几何？
**答：**设公鸡、母鸡、鸡仔的数目分别为 $x, y, z \in \Z$，那么根据题设有：
$$ 5x + 3y + \frac 1 3 z = 100 \\
x + y + z = 100 $$
消去 $z$ 得到 $14x + 8y = 200$ 即 $7 x + 4 y = 100$。
显然 $7 \perp 4$ 且 $1 = (- 1) \times 7 + 2 \times 4$。又 $100 = 100 \times 1$，因而一个非可行解 $x_0 = -100$，$y_0 = 200$。
因而所有解 $x = -100 - 4t$、$y = 200 + 7t$。
限定 $x, y \ge 0$ 和 $x + y \le 100$ 各自得到 $t \le -25$ 和 $t \ge -\frac {200}{7}$ 和 $t \le 0$。因而 $t = -25, -26, -27, -28$。因而解有：
$$ \begin{cases} x = 0 \\ y = 25 \\ z = 75 \end{cases}, \
\begin{cases} x = 4 \\ y = 18 \\ z = 78 \end{cases}, \
\begin{cases} x = 8 \\ y = 11 \\ z = 81 \end{cases}, \
\begin{cases} x = 12 \\ y = 4 \\ z = 84 \end{cases} $$
对于 $a, b, c \in \Z$ 且 $a,b >0$（注意正约束），研究其构成的二元一次丢番图方程
$$ ax + by = c $$
的非负整数解 $x, y$ 的性质。
【定理】对于 $a, b, c \in \Z$ 且 $a,b >1$、$a \perp b$，如果 $N > ab - a - b$，那么二元一次丢番图方程 $ax + by = N$ 有非负整数解。
证略。