aiwiki.page
中文
数学 / 代数与数论 / linear-diophantine-equation

线性丢番图方程

线性丢番图方程是系数为整数、且要求未知数取整数值的线性方程。

21 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
整数丢番图方程数论有理数实数线性方程组最大公约数线性组合线性丢番图…

线性丢番图方程是形如

a1x1+⋯+anxn=b,a_1x_1+\cdots+a_nx_n=b,

的方程,其中系数 a1,…,ana_1,\ldots,a_n 和常数 bb 都是整数,要求未知数 x1,…,xnx_1,\ldots,x_n 取整数值。它是丢番图方程的一次情形,也是数论的基本研究课题。与实数或有理数范围内的线性方程不同,它是否有解取决于整除关系。单个非平凡的线性丢番图方程有整数解,当且仅当其系数的最大公约数整除常数项。

定义与范围

“线性”是指每个未知数都只以一次幂出现,且未知数之间没有乘积项。例如,

6x+10y=146x+10y=14

是线性方程,而 x2+y2=14x^2+y^2=14 和 xy=14xy=14 则不是。

要求解为整数是这一概念的关键。例如,方程

6x+10y=76x+10y=7

在有理数和实数范围内有解,但没有整数解,因为其左端始终为偶数。

除非另有约束,未知数可以取负值或零。要求非负整数解、正整数解或指定范围内的解,限制条件都更严格,需要另行分析。

多个线性丢番图方程构成一个要求整数解的线性方程组,通常写成 Ax=bA\mathbf{x}=\mathbf{b}。

有解判据

设系数 a1,…,ana_1,\ldots,a_n 不全为零,并令

d=gcd⁡(a1,…,an)>0d=\gcd(a_1,\ldots,a_n)>0

为它们的最大公约数。那么,方程

a1x1+⋯+anxn=ba_1x_1+\cdots+a_nx_n=b

有整数解,当且仅当

d∣b.d\mid b.

必要性

由于 dd 整除每个系数 aia_i,它也整除这些系数的任意整数线性组合

a1x1+⋯+anxn.a_1x_1+\cdots+a_nx_n.

因此,只有当 dd 整除 bb 时,才可能存在整数解。

充分性

根据裴蜀等式,存在整数 u1,…,unu_1,\ldots,u_n,使得

a1u1+⋯+anun=d.a_1u_1+\cdots+a_nu_n=d.

若 b=kdb=kd,其中 kk 为整数,则将此等式两边乘以 kk,便得到一个解:

xi=kui,i=1,…,n.x_i=ku_i,\qquad i=1,\ldots,n.

等价地说,这些系数的整数线性组合所能表示的整数,恰好是它们的最大公约数的所有倍数。

若所有系数都为零,方程就化为 0=b0=b。此时,若 b=0b=0,任意整数元组都是解;若 b≠0b\ne0,则无解。

二元方程

经典的二元方程为

ax+by=c.ax+by=c.

假设 aa 和 bb 不全为零,并记

d=gcd⁡(a,b)>0.d=\gcd(a,b)>0.

若 d∤cd\nmid c,则没有整数解。若 d∣cd\mid c,且 (x0,y0)(x_0,y_0) 是一个解,则全部整数解为

x=x0+bdt,y=y0−adt,t∈Z.\boxed{ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb Z. }

因此,一个特解就能确定整个解集。

参数表示为何能涵盖全部解

先假设 aa 和 bb 均不为零。将另一组解 (x,y)(x,y) 所满足的方程,减去 (x0,y0)(x_0,y_0) 所满足的方程,得到

ad(x−x0)=−bd(y−y0).\frac{a}{d}(x-x_0) =-\frac{b}{d}(y-y_0).

整数 a/da/d 和 b/db/d 互素。因此,b/db/d 整除 x−x0x-x_0,于是

x−x0=bdtx-x_0=\frac{b}{d}t

对某个整数 tt 成立。代入后即可得到上述关于 y−y0y-y_0 的公式。反过来,直接代入便可验证,每个整数 tt 都对应一个解。

若某个系数为零,同样的参数表示仍然有效:系数非零的未知数取固定值,另一个未知数则可取任意整数。

示例

考虑方程

14x+21y=35.14x+21y=35.

由于 gcd⁡(14,21)=7\gcd(14,21)=7 且 7∣357\mid35,该方程有解。将等式

14(−1)+21(1)=714(-1)+21(1)=7

两边乘以 55,便得到特解 (−5,5)(-5,5)。因此,全部解为

x=−5+3t,y=5−2t,t∈Z.x=-5+3t,\qquad y=5-2t,\qquad t\in\mathbb Z.

例如,t=2t=2 时得到 (x,y)=(1,1)(x,y)=(1,1),t=1t=1 时得到 (−2,3)(-2,3)。相比之下,方程

14x+21y=3614x+21y=36

没有整数解,因为 77 不整除 3636。

解的计算

标准方法是使用扩展欧几里得算法。该算法不仅计算 d=gcd⁡(a,b)d=\gcd(a,b),还会求出整数 u,vu,v,使得

au+bv=d.au+bv=d.

求解步骤如下:

  1. 计算 d,u,vd,u,v。

  2. 检验是否有 d∣cd\mid c。

  3. 若成立,则取

    x0=ucd,y0=vcd.x_0=u\frac{c}{d},\qquad y_0=v\frac{c}{d}.
  4. 利用通解公式引入一个任意整数参数。

欧几里得算法所需的除法步数,与两个非零输入中较小者的绝对值呈对数关系。完整的位运算复杂度还取决于对所涉及整数进行算术运算的成本。

对于两个以上的系数,可以反复应用该算法:

gcd⁡(a1,a2,a3)=gcd⁡(gcd⁡(a1,a2),a3).\gcd(a_1,a_2,a_3) =\gcd\bigl(\gcd(a_1,a_2),a_3\bigr).

只要记录相应的等式,就能在满足整除判据时求出一个特解。

与同余的联系

当 b≠0b\ne0 时,方程

ax+by=cax+by=c

蕴含

ax≡c(mod∣b∣).ax\equiv c\pmod{|b|}.

反过来,任何满足这一同余式的整数 xx,都能给出整数

y=c−axb.y=\frac{c-ax}{b}.

因此,求解二元线性丢番图方程,与求解模算术中的一次同余方程密切相关。

对于正模数 mm,同余方程

ax≡c(modm)ax\equiv c\pmod m

有解,当且仅当 gcd⁡(a,m)∣c\gcd(a,m)\mid c。若有解,则它在模 mm 意义下恰有 gcd⁡(a,m)\gcd(a,m) 个不同的解类。

特别地,当 gcd⁡(a,m)=1\gcd(a,m)=1 时,可以利用裴蜀等式求出 aa 模 mm 的乘法逆元。这一联系也是中国剩余定理构造性求解方法的基础。

非负解与有界解

有整数解并不意味着有非负整数解。例如,方程

2x+3y=12x+3y=1

满足最大公约数判据,并且有解 (−1,1)(-1,1),但不存在同时满足 x≥0x\ge0 和 y≥0y\ge0 的解。

当 a,b>0a,b>0 时,将二元方程的参数表示代入非负约束,得到

x0+bdt≥0,y0−adt≥0.x_0+\frac{b}{d}t\ge0,\qquad y_0-\frac{a}{d}t\ge0.

因此,

⌈−dx0b⌉≤t≤⌊dy0a⌋.\left\lceil-\frac{dx_0}{b}\right\rceil \le t\le \left\lfloor\frac{dy_0}{a}\right\rfloor.

若将这两个端点分别记为 LL 和 UU,则非负解的个数为

max⁡(0,U−L+1).\max(0,U-L+1).

对于前面的例子 14x+21y=3514x+21y=35,由参数表示可得

t≥2,t≤2.t\ge2,\qquad t\le2.

因此,它唯一的非负解是 (1,1)(1,1)。若未知数还有额外的上界或下界约束,可以求出各约束对应的 tt 的区间,再取这些区间的交集。

一个相关问题是弗罗贝尼乌斯硬币问题。对于互素的正整数 a,b>1a,b>1,不能表示为

ax+by,x,y≥0,ax+by,\qquad x,y\ge0,

的最大整数为

ab−a−b.ab-a-b.

这一结论针对的是非负解;当 gcd⁡(a,b)=1\gcd(a,b)=1 时,无论右端取何整数,都存在不受符号限制的整数解。

多个未知数与格结构

对于含有 nn 个未知数、且至少有一个非零系数的单个方程,若解集非空,则其形式为

x0+L,\mathbf{x}_0+L,

其中

L={z∈Zn:a1z1+⋯+anzn=0}.L=\left\{\mathbf{z}\in\mathbb Z^n: a_1z_1+\cdots+a_nz_n=0\right\}.

集合 LL 是一个秩为 n−1n-1 的格。它有一组整数基 v1,…,vn−1\mathbf{v}_1,\ldots,\mathbf{v}_{n-1},从而

x=x0+t1v1+⋯+tn−1vn−1,ti∈Z.\mathbf{x} =\mathbf{x}_0+t_1\mathbf{v}_1+\cdots+t_{n-1}\mathbf{v}_{n-1}, \qquad t_i\in\mathbb Z.

从几何上看,该方程在实坐标空间中定义了一个超平面,而丢番图问题所问的是哪些整坐标点位于这个超平面上。当 n≥2n\ge2 时,每个有解的非平凡方程都有无穷多个不受额外约束的整数解。非负约束或有界性约束可能将这一集合缩减为有限个点,也可能使其变为空集。

整数格的一组基不能用实数范围内齐次解空间的任意一组有理基来替代。仅仅将一组有理基中的分母消去,所得向量可能只能生成整数解格的一个真子格。

方程组与史密斯标准形

对于方程组

Ax=b,A\mathbf{x}=\mathbf{b},

其中 AA 是整数矩阵,普通的高斯消元法可以判定它在有理数范围内是否有解,但仅靠这一方法无法确定其是否有整数解。

一种系统的整数求解方法是使用史密斯标准形。存在幺模整数矩阵 U,VU,V,即行列式为 11 或 −1-1 的整数矩阵,使得

UAV=D,UAV=D,

其中 DD 是矩形矩阵意义下的对角矩阵。它的非零对角元满足

d1∣d2∣⋯∣dr,d_1\mid d_2\mid\cdots\mid d_r,

这里 rr 是 AA 的秩。

令

x=Vy,c=Ub\mathbf{x}=V\mathbf{y},\qquad \mathbf{c}=U\mathbf{b}

便可将方程组化为

Dy=c.D\mathbf{y}=\mathbf{c}.

由于 UU 和 VV 都在整数坐标向量之间给出双射,该方程组有整数解,当且仅当

di∣ci(1≤i≤r),d_i\mid c_i\quad(1\le i\le r),

并且其余各行满足

ci=0(i>r)c_i=0\quad(i>r)

。y\mathbf{y} 中不受约束的坐标可作为参数,表示全部解。对于单个方程,唯一的非零史密斯不变量就是其系数的最大公约数。

应用与计算局限

线性丢番图方程可用于描述涉及不可分割数量的精确平衡条件,例如包装中的物品件数、支付问题中的货币面额、资源分配中的整数数量,以及周期性约束。

它们也是许多整数规划问题中的等式约束。在没有不等式或符号限制时,可以利用基于最大公约数和整数矩阵化简的系统方法,判定是否有解并给出解的参数表示。加入非负性约束、容量限制或优化目标后,问题就会发生显著变化。虽然二元情形仍可通过整数参数直接处理,但一般的整数规划在计算上可能十分困难。

关键在于区分两类问题:一类是寻找线性等式的整数解,另一类是寻找同时属于某个指定可行集的解。对于单个方程,最大公约数判据完全解决了前一类问题,却不能完全解决后一类问题。