• 对于 $a_1, a_2, \dots, a_n \neq 0$（$n \ge 2$），下面研究其构成的多元一次丢番图方程

  $$ a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = N $$

  的整数解 $x_1, x_2, \dots, x_n \in \Z$ 的性质。

一、多元一次丢番图方程解的结构

• 【多元一次丢番图方程有解的条件】多元一次丢番图方程 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = N$ 有整数解的充分必要条件为 ${\rm GCD} (a_1, a_2, \dots, a_n) \mid N$。

  **证：**记 GCD 分解 ${\rm GCD}(a_1, a_2, \dots, a_n) = d$，$a_1 = a_1' d$，$a_2 = a_2' d$，……，$a_{n} = a_{n}' d$。

  • $\Rightarrow$：如果方程存在整数解 $x_1^, x_2^, \dots, x_n^$，那么 $N = d (a'_1 x_1^ + a'_2 x_2^* + \cdots + a'_n x_n^*)$，因而 $d \mid N$。
  • $\Leftarrow$：由于 $d \mid N$，因而存在 $s \in \Z$ 使得 $N = sd$。根据裴蜀定理推广版，存在 $p_1, p_2, \dots, p_n \in \Z$ 使得 $d = p_1 a_1 + p_2 a_2 + \cdots + p_n a_n$，因而 $N = s p_1 a_1 + s p_2 a_2 + \cdots + s p_n a_n$，因而 $x_1^* = s p_1$，$x_2^* = s p_2$，……，$x_n^* = s p_n$ 是方程的一组解。

• 【多元一次丢番图方程解的结构】把系数看成整数行向量 $\boldsymbol a = [ a_1, a_2, \dots, a_n ]$。首先，存在一个可逆整数矩阵 $\boldsymbol U$，满足：① 行列式为 $\pm 1$；② $\boldsymbol a \boldsymbol U = [d, 0, 0, \dots, 0]$，其中 $d = {\rm GCD}(a_1, a_2, \dots, a_n)$。我们将 $\boldsymbol U$ 分解为列向量 $\boldsymbol U = [ \boldsymbol u_1, \boldsymbol u_2, \dots, \boldsymbol u_n ]$，那么其次：对于任意整数列向量 $\boldsymbol x = [ x_1, x_2, \dots, x_n ]^{\rm T} \in \Z^n$，它是方程的解当且仅当：

  $$ \exists t_2, t_3, \dots, t_n \in \Z, \quad \boldsymbol x = \frac {N}{d} \boldsymbol u_1 + t_2 \boldsymbol u_2 + t_3 \boldsymbol u_3 + \cdots + t_n \boldsymbol u_n $$

  证：

  • 关于 $N/d$：我们已经证明了方程有整数解当且仅当 $d \mid N$，因而 $N/d$ 是一个整数。
  • 先讨论这样的 $\boldsymbol U$ 的存在性。

    • 先给出 $n = 2$ 时的引理：给定 $p, q \in \Z$，令 $g = {\rm GCD} (p, q)$，那么存在一个 $2 \times 2$ 的可逆整数矩阵 $\boldsymbol M$ 满足：① 行列式为 $1$；② $[p, q] \boldsymbol M = [g, 0]$。

      证明

      由裴蜀定理，存在 $r, s \in \Z$ 使得 $g = pr + qs$，记分解式 $p = p_1 g$、$q = q_1 g$。构造

      $$ \boldsymbol M = \begin{bmatrix}

      r & -q_1 \\ s & p_1

      \end{bmatrix} $$

      那么可以验证 $[p, q] \boldsymbol M = [pr + qs , -gp_1q_1 + gq_1p_1] = [g, 0]$，并且 $\det \boldsymbol M = rp_1 + sq_1 = \frac {pr + qs}{g} = \frac g g = 1$。根据 $\det \boldsymbol M \neq 0$ 当然 $\boldsymbol M$ 就可逆。$\boldsymbol M$ 也由整数构成。

    • $n > 2$ 时，通过下面的算法每次消去一个列来实现。

      • 初始时，令 $\boldsymbol b^{(1)} := \boldsymbol a = [a_1, a_2, \dots, a_n]$，$\boldsymbol U^{(1)} := \boldsymbol I _n$。
      • 对 $k = 2, 3, \cdots, n$，做如下步骤：
        • 记录下上一步 $\boldsymbol b^{(k-1)}$ 的第 $1$ 个分量和第 $k$ 个分量：$p^{(k)} := b_1^{(k - 1)}$、$q^{(k)} := b_k^{(k - 1)}$。
        • 用上面的引理，取 $2 \times 2$ 的可逆整数矩阵 $\boldsymbol M^{(k)}$ 使得 ① 行列式为 $1$；② $[p^{(k)}, q^{(k)}] \boldsymbol M^{(k)} = [{\rm GCD}(p^{(k)}, q^{(k)}), 0]$。
        • 把 $\boldsymbol M^{(k)}$ 嵌入到 $n \times n$ 单位矩阵中，使之成为一个只会作用在第 $1$ 项和第 $k$ 项上的矩阵 $\boldsymbol E^{(k)}$：
          • 在 $(1, 1), (1, k), (k, 1), (k, k)$ 这四个位置放上 $\boldsymbol M^{(k)}$ 的四个元素。
          • 其余对角线上为 $1$，非对角线为 $0$。
        • 更新 $\boldsymbol b^{(k)} = \boldsymbol b^{(k-1)} \boldsymbol E^{(k)}$ 和 $\boldsymbol U^{(k)} = \boldsymbol U^{(k-1)} \boldsymbol E^{(k)}$。可以发现：
          • $\boldsymbol E^{(k)}$ 能将 $\boldsymbol b^{(k-1)}$ 的第 $k$ 项化为 $0$，并为第 $1$ 项多套一层 ${\rm GCD}$ 也就是多一个求 ${\rm GCD}$ 的项目。
          • $\det \boldsymbol E^{(k)} = \det \boldsymbol M^{(k)} = 1$（证略，据说可以使用行列式的 Leibniz 公式）。
      • 结束时，证明 $\boldsymbol U^{(n)}$ 就是我们要的 $\boldsymbol U$：
        • $\boldsymbol U^{(n)} = \boldsymbol E^{(1)} \boldsymbol E^{(2)} \cdots \boldsymbol E^{(n)}$，有 $\boldsymbol U^{(n)} = \boldsymbol E^{(1)} \boldsymbol E^{(2)} \cdots \boldsymbol E^{(n)}$，因而 $\det \boldsymbol U^{(n)} = (\det \boldsymbol E^{(1)}) (\det \boldsymbol E^{(2)}) \cdots (\det \boldsymbol E^{(n)}) = 1$。
        • $\boldsymbol b^{(k)} = \boldsymbol a \boldsymbol E^{(1)} \boldsymbol E^{(2)} \cdots \boldsymbol E^{(n)} = \boldsymbol a \boldsymbol U^{(n)}$，且根据上面提到的每一步的变化， $\boldsymbol a \boldsymbol E^{(1)} \boldsymbol E^{(2)} \cdots \boldsymbol E^{(n)} = [d, 0, 0, \dots, 0]$。
  • 然后讨论方程的解的结构。

    • 关键事实：$\boldsymbol U^{-1}$ 还是整数矩阵。据此记录整数向量 $\boldsymbol y = \boldsymbol U^{-1} \boldsymbol x$，可知 $\boldsymbol x = \boldsymbol U \boldsymbol y$。

      证明：

      $$ \boldsymbol U^{-1} = \frac {{\rm adj} \, \boldsymbol U}{\det \boldsymbol U} $$

      而 ${\rm adj} \, \boldsymbol U$ 根据计算过程可以知道它的所有元素都是整数，又 $\det \boldsymbol U = 1$，那么 $\boldsymbol U^{-1}$ 是整数矩阵。

    • $\Rightarrow$：$\boldsymbol x$ 是方程的解，即 $\boldsymbol a \boldsymbol x = N$。即 $\boldsymbol a\boldsymbol U \boldsymbol y = N$。即 $[d, 0, 0, \dots, 0] \boldsymbol y = N$。即 $d y_1 = N$。方程有解导出 $d \mid N$，因而 $y_1$ 就是分解时的 $N_0 = N/d$。因而

      $$ \boldsymbol x = \boldsymbol U \boldsymbol y = \frac N d \boldsymbol u_1 + y_2 \boldsymbol u_2 + y_3 \boldsymbol u_3 + \cdots + y_n \boldsymbol u_n $$

      即目标条件成立。

    • $\Leftarrow$：设 $\exists t_2, t_3, \dots, t_n \in \Z$ 使得 $\boldsymbol x = \frac {N}{d} \boldsymbol u_1 + t_2 \boldsymbol u_2 + t_3 \boldsymbol u_3 + \cdots + t_n \boldsymbol u_n$。那么：

      $$ \begin{align*}

      \boldsymbol a \boldsymbol x &= \boldsymbol a \left( \frac {N}{d} \boldsymbol u_1 + \sum_{i=2}^n t_i \boldsymbol u_i \right ) \\

      &= \frac {N}{d} \boldsymbol a \boldsymbol u_1 + \sum_{i=2}^n t_i \boldsymbol a \boldsymbol u_i \\

      &= \frac N d \cdot d + 0 \\

      &= N

      \end{align*} $$

      即 $\boldsymbol x$ 是方程的一个解。