5.4.2 线性丢番图方程

1. 丢番图方程

方程 $f (x_{1}, x_{2}, \dots, x_{n}) = b$ 称作 $n$ 个未知数的丢番图 (Diophantine) 方程,当且仅当 $f (x_{1}, x_{2}, \dots, x_{n})$ 是 $x_{1}, x_{2}, \dots, x_{n}$ 的系数在整数集 $Z$ 中的多项式, $b$ 是一个整常数, 并且仅考虑整数解. 命名 “丢番图” 是为纪念希腊数学家丢番图, 他生活在公元 250 年前后.

在实际中, 丢番图方程出现在, 例如, 数量之间关系的刻画中. 迄今只有 2 个未知数并且至多两次的丢番图方程的一般解是已知的. 仅在特殊情形才知道高次丢番图方程的解.

2. $n$ 个未知数的线性丢番图方程

$n$ 个未知数的线性丢番图方程是指形如

\begin{matrix} (5.240) & a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b (a_{i} \in Z, b \in Z) \end{matrix}

的方程, 这里仅求整数解. 下面给出它的解法.

3. 可解性条件

如果系数 $a_{i}$ 不全为零,那么丢番图方程 (5.240) 可解,当且仅当 $gcd (a_{1}, a_{2}, \dots$ , $a_{n})$ 是 $b$ 的因子.

$114 x + 315 y = 3$ 可解,因为 $gcd (114, 315) = 3$ .

如果一个含 $n (n > 1)$ 个未知数的线性丢番图方程有解,而 $Z$ 是变量区域,那么方程有无穷多解. 于是在解集中有 $n - 1$ 个自由变量. 对于 $Z$ 的子集,这个命题不正确.

4. $n = 2$ 时的解法

设

\begin{matrix} (5.241a) & a_{1} x_{1} + a_{2} x_{2} = b (a_{1}, a_{2}) \neq (0, 0) \end{matrix}

是一个可解的丢番图方程,即有 $gcd (a_{1}, a_{2}) ∣ b$ . 为了求方程的特解,用 $gcd (a_{1}, a_{2})$ 除方程,我们得到 $a_{1}^{'} x_{1} + a_{2}^{'} x_{2} = b^{'}$ ,其中 $gcd (a_{1}^{'}, a_{2}^{'}) = 1$ . 如在第 500 页 5.4.1.4,4. 中所指出的,确定 $gcd (a_{1}^{'}, a_{2}^{'})$ 最终可得到 $a_{1}^{'}$ 和 $a_{2}^{'}$ 的线性组合: $a_{1}^{'} c_{1}^{'} + a_{2}^{'} c_{2}^{'} = 1$ . 代入给定方程可以证明有序整数对 $(c_{1}^{'} b^{'}, c_{2}^{'} b^{'})$ 是所给丢番图方程的一组解.

$114 x + 315 y = 6$ . 因为 $3 = gcd (114, 315)$ ,所以用 3 除方程. 这蕴涵 $38 x +$ $105 y = 2$ ,以及 $38 \cdot 47 + 105 \cdot (- 17) = 1$ (参见第 500 页 5.4.1.4,4.). 有序组 $(47 \cdot 2, (- 17) \cdot 2) = (94, - 34)$ 是方程 $114 x + 315 y = 6$ 的一个特解.

可求得(5.241a)的解集如下: 如果 $(x_{1}^{0}, x_{2}^{0})$ 是任意一个特解,它也可以用平凡的方法得到, 那么

\begin{matrix} (5.241b) & {(x_{1}^{0} + t \cdot a_{2}^{'}, x_{2}^{0} - t \cdot a_{1}^{'}) ∣ t \in Z} \end{matrix}

是所有解的集合.

$◼$ 方程 $114 x + 315 y = 6$ 的解集是 ${(94 + 315 t, - 34 - 114 t) ∣ t \in Z}$ .

5. $n > 2$ 时的归约方法

设给定可解的丢番图方程

\begin{matrix} (5.242a) & a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b, \end{matrix}

其中 $(a_{1}, a_{2}, \dots, a_{n}) \neq (0, 0, \dots, 0)$ ,并且 $gcd (a_{1}, a_{2}, \dots, a_{n}) = 1$ . 如果 $gcd (a_{1}$ , $a_{2}, \dots, a_{n}) \neq 1$ ,那么可用 $gcd (a_{1}, a_{2}, \dots, a_{n})$ 除方程. 作变换

\begin{matrix} (5.242b) & a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n - 1} x_{n - 1} = b - a_{n} x_{n} \end{matrix}

后,将 $x_{n}$ 看作一个整常数,得到一个含有 $n - 1$ 个变量的线性丢番图方程,因而它当且仅当 $gcd (a_{1}, a_{2}, \dots, a_{n - 1})$ 整除 $b - a_{n} x_{n}$ 时可解.

条件

\begin{matrix} (5.242c) & gcd (a_{1}, a_{2}, \dots, a_{n - 1}) ∣ b - a_{n} x_{n} \end{matrix}

被满足,当且仅当存在整数 $\underset{―}{c}, {\underset{―}{c}}_{n}$ 使得

\begin{matrix} (5.242d) & gcd (a_{1}, a_{2}, \dots, a_{n - 1}) \cdot \underset{―}{c} + a_{n} \cdot {\underset{―}{c}}_{n} = b . \end{matrix}

这是两个未知数的线性丢番图方程, 并且它可以如同第 503 页 5.4.2, 4. 那样求解. 如果确定了它的解,那么剩下要解只有 $n - 1$ 个未知数的丢番图方程. 继续这个过程直到得到两个未知数的丢番图方程, 这可用第 503 页 5.4.2, 4. 给出的方法求解. 最后, 所给方程的解由这样得到的解集构造出来.

解丢番图方程

\begin{matrix} (5.243a) & 2 x + 4 y + 3 z = 3. \end{matrix}

因为 $gcd (2, 4, 3) = 1$ 是 3 的因子,所以这个方程可解. 未知数为 $x, y$ 的丢番图方程

\begin{matrix} (5.243b) & 2 x + 4 y = 3 - 3 z \end{matrix}

当且仅当 $gcd (2, 4)$ 是 $3 - 3 z$ 的因子时可解. 对应的丢番图方程 $2 z^{'} + 3 z = 3$ 有解集 ${(- 3 + 3 t, 3 - 2 t) ∣ t \in Z}$ . 这蕴涵 $z = 3 - 2 t$ ,并且现在要对于每个 $t \in Z$ 求出可解丢番图方程 $2 x + 4 y = 3 - 3 (2 t)$ 或

\begin{matrix} (5.243c) & x + 2 y = - 3 + 3 t \end{matrix}

的解. 因为 $gcd (1, 2) = 1 ∣ (- 3 + 3 t)$ ,所以方程(5.243c)可解. 现在有 $1 \cdot (- 1) + 2 \cdot 1 = 1$ , 以及 $1 \cdot (3 - 3 t) + 2 \cdot (- 3 + 3 t) = - 3 + 3 t$ . 解集是 ${((3 - 3 t) + 2 s, (- 3 + 3 t) - s) ∣ s \in Z}$ . 这蕴涵 $x = (3 - 3 t) + 2 s, y = (- 3 + 3 t) - s$ ,并且这样得到的 ${(3 - 3 t + 2 s, - 3 +$ $3 t - s, 3 - 2 t) ∣ s, t \in Z}$ 就是(5.243a)的解集.

5.4.2 线性丢番图方程 ​

1. 丢番图方程 ​

2. n 个未知数的线性丢番图方程 ​

3. 可解性条件 ​

4. n=2 时的解法 ​