aiwiki.page
中文
数学 / 代数与数论 / bezouts-identity

贝祖等式

贝祖等式将整数的最大公约数表示为它们的整系数线性组合,联系了整除性、丢番图方程与模逆元。

21 个关键词9 个词条链接到这里1 个尚未撰写AI 撰写
整数最大公约数数论线性组合互素整数数学证明欧几里得算法丢番图方程贝祖等式

贝祖等式指出,对于任意两个不全为零的整数 aa 和 bb,存在整数 xx 和 yy,使得

ax+by=gcd⁡(a,b).ax+by=\gcd(a,b).

这里,gcd⁡(a,b)\gcd(a,b) 是 aa 和 bb 的正的最大公约数。整数 xx 和 yy 称为贝祖系数。作为数论中的一项基本结论,贝祖等式将整除性与整系数线性组合联系起来,并为求解线性丢番图方程和求模逆元提供了构造性基础。

表述与含义

设 d=gcd⁡(a,b)d=\gcd(a,b)。贝祖等式断言,dd 可以表示为 aa 的某个整数倍与 bb 的某个整数倍之和。更强的结论是,所有这类组合构成的集合,恰好就是 dd 的所有倍数构成的集合:

{ax+by:x,y∈Z}=dZ.\{ax+by:x,y\in\mathbb Z\}=d\mathbb Z.

这一结论包含两部分:

  • 每个整系数组合 ax+byax+by 都能被 dd 整除,因为 dd 同时整除 aa 和 bb。
  • dd 的每个倍数都是 aa 和 bb 的整系数组合,因为可以将等式 ax0+by0=dax_0+by_0=d 的两边同乘任意整数。

因此,dd 是 aa 和 bb 的整系数组合所能取到的最小正值。

例如,

54(−1)+24(2)=−6,54(-1)+24(2)=-6,

而

54(1)+24(−2)=6=gcd⁡(54,24).54(1)+24(-2)=6=\gcd(54,24).

所以,11 和 −2-2 是 5454 和 2424 的一组贝祖系数。

这些系数不一定为正,也不唯一。事实上,如果将两个系数都限制为非负整数,等式通常就无法成立。

互质整数

如果两个整数的最大公约数为 11,就称它们是互质整数。贝祖等式给出了如下等价关系:

gcd⁡(a,b)=1⟺ax+by=1 for some x,y∈Z.\gcd(a,b)=1 \quad\Longleftrightarrow\quad ax+by=1 \text{ for some }x,y\in\mathbb Z.

反向推论显然成立:aa 和 bb 的任意公约数都必须整除 ax+by=1ax+by=1。

如果 a,ba,b 中恰有一个为零,等式仍然成立。例如,若 a≠0a\ne0 且 b=0b=0,可取 x=a/∣a∣x=a/|a|、y=0y=0。若约定 gcd⁡(0,0)=0\gcd(0,0)=0,那么在 a=b=0a=b=0 时等式也显然成立,只是此时不再适用最小正值的解释。

利用最小正值的证明

考虑集合

S={ax+by:x,y∈Z, ax+by>0}.S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.

由于 aa 和 bb 不全为零,SS 非空。根据正整数的良序性,SS 有最小元素,记为

m=ax0+by0.m=ax_0+by_0.

用 mm 对 aa 作带余除法:

a=qm+r,0≤r<m.a=qm+r,\qquad 0\le r<m.

于是

r=a−qm=a(1−qx0)+b(−qy0).r=a-qm =a(1-qx_0)+b(-qy_0).

如果 r>0r>0,那么它就是 SS 中一个比 mm 更小的元素,与 mm 的选取矛盾。因此 r=0r=0,即 m∣am\mid a。同理可得 m∣bm\mid b。

aa 和 bb 的每个公约数都整除 m=ax0+by0m=ax_0+by_0。由于 mm 本身也是一个正公约数,因此

m=gcd⁡(a,b).m=\gcd(a,b).

这一数学证明无需先给出求系数的算法,就能确立系数的存在性。

用扩展欧几里得算法计算

欧几里得算法通过反复作带余除法求出最大公约数。其扩展形式还能求出贝祖系数,方法是回代,或在除法过程中同步记录系数。

对于 a=240a=240 和 b=46b=46,带余除法的过程为

240=5⋅46+10,46=4⋅10+6,10=1⋅6+4,6=1⋅4+2,4=2⋅2.\begin{aligned} 240&=5\cdot46+10,\\ 46&=4\cdot10+6,\\ 10&=1\cdot6+4,\\ 6&=1\cdot4+2,\\ 4&=2\cdot2. \end{aligned}

最后一个非零余数是 22。回代得到

2=6−4=2⋅6−10=2⋅46−9⋅10=47⋅46−9⋅240.\begin{aligned} 2&=6-4\\ &=2\cdot6-10\\ &=2\cdot46-9\cdot10\\ &=47\cdot46-9\cdot240. \end{aligned}

因此

240(−9)+46(47)=2.240(-9)+46(47)=2.

正向计算的实现方式始终维护如下表示:

ri=sia+tib.r_i=s_i a+t_i b.

从

(r0,s0,t0)=(a,1,0),(r1,s1,t1)=(b,0,1),(r_0,s_0,t_0)=(a,1,0),\qquad (r_1,s_1,t_1)=(b,0,1),

开始,每一步除法都按下式更新:

ri+1=ri−1−qiri,si+1=si−1−qisi,ti+1=ti−1−qiti.\begin{aligned} r_{i+1}&=r_{i-1}-q_i r_i,\\ s_{i+1}&=s_{i-1}-q_i s_i,\\ t_{i+1}&=t_{i-1}-q_i t_i. \end{aligned}

最后一个非零余数所对应的系数对,就给出了所需的等式;如果该余数为负,则需调整符号。

系数的非唯一性与所有系数对

假设

ax0+by0=d,d=gcd⁡(a,b)>0.ax_0+by_0=d,\qquad d=\gcd(a,b)>0.

那么,ax+by=dax+by=d 的全部整数解为

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

代入即可验证,这些系数对使 ax+byax+by 的值保持不变。反过来,将两个解对应的等式相减,得到

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

由于 a/da/d 和 b/db/d 互质,利用它们的整除性质即可推出上述参数表示。

对于 240x+46y=2240x+46y=2,这一表示为

x=−9+23t,y=47−120t.x=-9+23t,\qquad y=47-120t.

因此,贝祖系数本身并没有唯一指定的一对;采用不同的计算约定,可能得到不同但同样有效的系数对。

应用

线性丢番图方程

线性丢番图方程

ax+by=cax+by=c

有整数解的充要条件是

gcd⁡(a,b)∣c.\gcd(a,b)\mid c.

必要性在于,a,ba,b 的每个公约数都整除左边。为证明充分性,将 cc 写成 c=kdc=kd,并将贝祖等式两边同乘 kk:

a(kx0)+b(ky0)=c.a(kx_0)+b(ky_0)=c.

因此,全部解为

x=kx0+bdt,y=ky0−adt,t∈Z.x=kx_0+\frac{b}{d}t,\qquad y=ky_0-\frac{a}{d}t, \qquad t\in\mathbb Z.

模逆元

在模算术中,对于整数 m≥2m\ge2,aa 的模乘法逆元是满足下式的整数 uu:

au≡1(modm).au\equiv1\pmod m.

这样的逆元存在,当且仅当 gcd⁡(a,m)=1\gcd(a,m)=1。

贝祖等式

au+mv=1au+mv=1

直接给出了模 mm 的逆元 uu。例如,

3(5)+7(−2)=13(5)+7(-2)=1

表明 55 是 33 模 77 的逆元。

互质消去与素数的整除性质

如果 gcd⁡(a,b)=1\gcd(a,b)=1 且 a∣bca\mid bc,那么 a∣ca\mid c。证明只需将 ax+by=1ax+by=1 两边同乘 cc:

acx+bcy=c.acx+bcy=c.

左边两项都能被 aa 整除。

对于素数 pp,由此可得欧几里得引理:

p∣ab⟹p∣a or p∣b.p\mid ab\quad\Longrightarrow\quad p\mid a\ \text{or}\ p\mid b.

这一整除原理是算术基本定理中唯一性结论的关键。

中国剩余定理

贝祖系数为中国剩余定理提供了显式构造。如果 gcd⁡(m,n)=1\gcd(m,n)=1,且

um+vn=1,um+vn=1,

那么同余方程组

z≡r(modm),z≡s(modn)z\equiv r\pmod m,\qquad z\equiv s\pmod n

的一个解为

z=rvn+sum.z=rvn+sum.

该解在模 mnmn 的意义下唯一。

推广

两个以上的整数

对于不全为零的整数 a1,…,ana_1,\ldots,a_n,存在整数 x1,…,xnx_1,\ldots,x_n,使得

a1x1+⋯+anxn=gcd⁡(a1,…,an).a_1x_1+\cdots+a_nx_n=\gcd(a_1,\ldots,a_n).

利用

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

反复应用两个整数的贝祖等式,即可得到这一结论。

特别地,这些整数的最大公约数为 11,当且仅当它们的某个整系数组合等于 11。整体互质并不要求两两互质:6,10,156,10,15 的最大公约数为 11,并且

6+10−15=1,6+10-15=1,

但其中任意两个数都有大于 11 的公约数。

域上的多项式

如果 f,gf,g 是域(数学) FF 上不全为零的一元多项式,那么存在 u,v∈F[x]u,v\in F[x],使得

uf+vg=gcd⁡(f,g).uf+vg=\gcd(f,g).

通常约定将最大公约式规范化为首一多项式。与整数情形一样,通过多项式除法和扩展欧几里得算法即可确立这一等式。

例如,在 Q[x]\mathbb Q[x] 中,

(x2+1)−x(x)=1,(x^2+1)-x(x)=1,

所以 x2+1x^2+1 与 xx 互质。

理想与贝祖整环

用抽象代数的语言来说,整数的贝祖等式意味着

(a,b)=(d),(a,b)=(d),

其中,(a,b)(a,b) 是由 a,ba,b 生成的理想(环论),而 (d)(d) 由它们的最大公约数的所有倍数组成。

每个主理想整环都具有同样的性质。更一般地,**贝祖整环**是指每个有限生成理想都是主理想的整环。每个主理想整环都是贝祖整环,但反之不一定成立。

仅有最大公约数的存在性,并不能保证贝祖等式成立。在多项式环(数学) Q[s,t]\mathbb Q[s,t] 中,多项式 ss 和 tt 的最大公约式为 11,但不存在多项式 u,vu,v 满足

su+tv=1.su+tv=1.

因为代入 s=t=0s=t=0 就会得到 0=10=1。这体现了域上一元多项式情形与多元多项式情形的区别。

命名与历史背景

这一等式以法国数学家艾蒂安·贝祖的名字命名,他的研究包含了这一结论的多项式形式。整数形式的结论在他之前就已出现,并与古老的欧几里得算法密切相关。它不同于代数几何中的贝祖定理,后者讨论的是代数曲线的相交问题。