# 线性不定方程面试题
> 答案来自ChatGPT-4o
这是一个关于**线性不定方程整数解**的问题。我们分析如下：
---
### 一、问题描述
你给出的形式是：
$$
\sum_{i=1}^N a_i x_i = C
$$
其中：
* $x_i \in \mathbb{Z}$：未知整数变量；
* $a_i \in \mathbb{Z}$：常系数；
* $C \in \mathbb{Z}$：常数项；
这是一个**一元线性组合等于定值的整数解问题**，即一个**线性不定方程**。
---
### 二、是否有解？——与裴蜀定理有关
是的，这个问题**与裴蜀定理密切相关**。
> \*\*裴蜀定理（Bézout's Identity）\*\*指出：
> 若 $\gcd(a_1, a_2, \dots, a_n) = d$，那么对于任意整数 $C$，线性方程：
>
> $$
> a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = C
> $$
>
> 有整数解当且仅当 $d \mid C$（即 $d$ 整除 $C$）。
所以，**解的存在性条件**为：
$$
\gcd(a_1, a_2, \dots, a_n) \mid C
$$
---
### 三、如何求解？——与扩展欧几里得算法有关
是的，**扩展欧几里得算法（Extended Euclidean Algorithm）用于求两个数的整数解**（即 $a x + b y = \gcd(a,b)$ 的一组整数解），在这个多元问题中也有用，尤其是用于递归构造整数解。
#### 举个例子（两元情形）：
方程：
$$
a x + b y = C
$$
若 $d = \gcd(a,b) \mid C$，那么令 $a' = \frac{a}{d}, b' = \frac{b}{d}, C' = \frac{C}{d}$，则求解：
$$
a' x + b' y = C'
$$
1. 先用扩展欧几里得算法求出 $a' x_0 + b' y_0 = 1$ 的一组解；
2. 乘以 $C'$：得到一个特解 $x = x_0 C', y = y_0 C'$；
3. 通解为：
$$
x = x_0 C' + k \cdot \frac{b}{d},\quad y = y_0 C' - k \cdot \frac{a}{d},\quad k \in \mathbb{Z}
$$
---
### 四、多元情形的一般方法（递归法）
对于多于两个变量的情形，如：
$$
a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = C
$$
可以采用以下思路：
1. **使用扩展欧几里得算法递归合并变量**：
* 第一步求解 $a_1 x_1 + a_2 x_2 = d_{12}$ 的整数解；
* 再将该结果合并为 $d_{12} x_{12} + a_3 x_3 = d_{123}$，继续解下去；
* 最后得出 $\gcd(a_1, ..., a_n)$ 与 C 的关系；
* 如果存在整数解，则反向代回得到通解；
2. 或者使用**整数解空间的生成元表示**：
* 先求出一个特解；
* 然后求出齐次方程 $\sum a_i x_i = 0$ 的所有整数解组成的自由 abelian 群（即解空间）；
* 通解 = 特解 + 齐次解空间的所有解。
---
### 五、总结关系
| 项目 | 说明 |
| -------- | -------------------- |
| 裴蜀定理 | 判断整数解是否存在（是否可解） |
| 扩展欧几里得算法 | 求两数线性方程的整数解（特解 + 通解） |
| 多元情况处理 | 通过递归、构造齐次解空间、数论方法等 |
---
### 六、建议工具
* 对于手动求解两三个变量的问题，手工+扩展欧几里得足够；
* 多变量时，可用：
* 模块方程变换；
* 数学软件（如 SageMath、Mathematica、SymPy）中的 `diophantine` 解法；
* 矩阵方法（Smith Normal Form）等高级技巧。
---
![]()