贝祖等式指出,对于任意两个不全为零的整数 a 和 b,存在整数 x 和 y,使得
ax+by=gcd(a,b).
这里,gcd(a,b) 是 a 和 b 的正的最大公约数。整数 x 和 y 称为贝祖系数。作为数论中的一项基本结论,贝祖等式将整除性与整系数线性组合联系起来,并为求解线性丢番图方程和求模逆元提供了构造性基础。
表述与含义
设 d=gcd(a,b)。贝祖等式断言,d 可以表示为 a 的某个整数倍与 b 的某个整数倍之和。更强的结论是,所有这类组合构成的集合,恰好就是 d 的所有倍数构成的集合:
{ax+by:x,y∈Z}=dZ.
这一结论包含两部分:
- 每个整系数组合 ax+by 都能被 d 整除,因为 d 同时整除 a 和 b。
- d 的每个倍数都是 a 和 b 的整系数组合,因为可以将等式 ax0+by0=d 的两边同乘任意整数。
因此,d 是 a 和 b 的整系数组合所能取到的最小正值。
例如,
54(−1)+24(2)=−6,
而
54(1)+24(−2)=6=gcd(54,24).
所以,1 和 −2 是 54 和 24 的一组贝祖系数。
这些系数不一定为正,也不唯一。事实上,如果将两个系数都限制为非负整数,等式通常就无法成立。
互质整数
如果两个整数的最大公约数为 1,就称它们是互质整数。贝祖等式给出了如下等价关系:
gcd(a,b)=1⟺ax+by=1 for some x,y∈Z.
反向推论显然成立:a 和 b 的任意公约数都必须整除 ax+by=1。
如果 a,b 中恰有一个为零,等式仍然成立。例如,若 a=0 且 b=0,可取 x=a/∣a∣、y=0。若约定 gcd(0,0)=0,那么在 a=b=0 时等式也显然成立,只是此时不再适用最小正值的解释。
利用最小正值的证明
考虑集合
S={ax+by:x,y∈Z, ax+by>0}.
由于 a 和 b 不全为零,S 非空。根据正整数的良序性,S 有最小元素,记为
m=ax0+by0.
用 m 对 a 作带余除法:
a=qm+r,0≤r<m.
于是
r=a−qm=a(1−qx0)+b(−qy0).
如果 r>0,那么它就是 S 中一个比 m 更小的元素,与 m 的选取矛盾。因此 r=0,即 m∣a。同理可得 m∣b。
a 和 b 的每个公约数都整除 m=ax0+by0。由于 m 本身也是一个正公约数,因此
m=gcd(a,b).
这一数学证明无需先给出求系数的算法,就能确立系数的存在性。
用扩展欧几里得算法计算
欧几里得算法通过反复作带余除法求出最大公约数。其扩展形式还能求出贝祖系数,方法是回代,或在除法过程中同步记录系数。
对于 a=240 和 b=46,带余除法的过程为
240461064=5⋅46+10,=4⋅10+6,=1⋅6+4,=1⋅4+2,=2⋅2.
最后一个非零余数是 2。回代得到
2=6−4=2⋅6−10=2⋅46−9⋅10=47⋅46−9⋅240.
因此
240(−9)+46(47)=2.
正向计算的实现方式始终维护如下表示:
ri=sia+tib.
从
(r0,s0,t0)=(a,1,0),(r1,s1,t1)=(b,0,1),
开始,每一步除法都按下式更新:
ri+1si+1ti+1=ri−1−qiri,=si−1−qisi,=ti−1−qiti.
最后一个非零余数所对应的系数对,就给出了所需的等式;如果该余数为负,则需调整符号。
系数的非唯一性与所有系数对
假设
ax0+by0=d,d=gcd(a,b)>0.
那么,ax+by=d 的全部整数解为
x=x0+dbt,y=y0−dat,t∈Z.
代入即可验证,这些系数对使 ax+by 的值保持不变。反过来,将两个解对应的等式相减,得到
da(x−x0)=−db(y−y0).
由于 a/d 和 b/d 互质,利用它们的整除性质即可推出上述参数表示。
对于 240x+46y=2,这一表示为
x=−9+23t,y=47−120t.
因此,贝祖系数本身并没有唯一指定的一对;采用不同的计算约定,可能得到不同但同样有效的系数对。
应用
线性丢番图方程
线性丢番图方程
有整数解的充要条件是
gcd(a,b)∣c.
必要性在于,a,b 的每个公约数都整除左边。为证明充分性,将 c 写成 c=kd,并将贝祖等式两边同乘 k:
a(kx0)+b(ky0)=c.
因此,全部解为
x=kx0+dbt,y=ky0−dat,t∈Z.
模逆元
在模算术中,对于整数 m≥2,a 的模乘法逆元是满足下式的整数 u:
au≡1(modm).
这样的逆元存在,当且仅当 gcd(a,m)=1。
贝祖等式
直接给出了模 m 的逆元 u。例如,
3(5)+7(−2)=1
表明 5 是 3 模 7 的逆元。
互质消去与素数的整除性质
如果 gcd(a,b)=1 且 a∣bc,那么 a∣c。证明只需将 ax+by=1 两边同乘 c:
acx+bcy=c.
左边两项都能被 a 整除。
对于素数 p,由此可得欧几里得引理:
p∣ab⟹p∣a or p∣b.
这一整除原理是算术基本定理中唯一性结论的关键。
中国剩余定理
贝祖系数为中国剩余定理提供了显式构造。如果 gcd(m,n)=1,且
那么同余方程组
z≡r(modm),z≡s(modn)
的一个解为
z=rvn+sum.
该解在模 mn 的意义下唯一。
推广
两个以上的整数
对于不全为零的整数 a1,…,an,存在整数 x1,…,xn,使得
a1x1+⋯+anxn=gcd(a1,…,an).
利用
gcd(a1,a2,a3)=gcd(gcd(a1,a2),a3).
反复应用两个整数的贝祖等式,即可得到这一结论。
特别地,这些整数的最大公约数为 1,当且仅当它们的某个整系数组合等于 1。整体互质并不要求两两互质:6,10,15 的最大公约数为 1,并且
6+10−15=1,
但其中任意两个数都有大于 1 的公约数。
域上的多项式
如果 f,g 是域(数学) F 上不全为零的一元多项式,那么存在 u,v∈F[x],使得
uf+vg=gcd(f,g).
通常约定将最大公约式规范化为首一多项式。与整数情形一样,通过多项式除法和扩展欧几里得算法即可确立这一等式。
例如,在 Q[x] 中,
(x2+1)−x(x)=1,
所以 x2+1 与 x 互质。
理想与贝祖整环
用抽象代数的语言来说,整数的贝祖等式意味着
(a,b)=(d),
其中,(a,b) 是由 a,b 生成的理想(环论),而 (d) 由它们的最大公约数的所有倍数组成。
每个主理想整环都具有同样的性质。更一般地,**贝祖整环**是指每个有限生成理想都是主理想的整环。每个主理想整环都是贝祖整环,但反之不一定成立。
仅有最大公约数的存在性,并不能保证贝祖等式成立。在多项式环(数学) Q[s,t] 中,多项式 s 和 t 的最大公约式为 1,但不存在多项式 u,v 满足
因为代入 s=t=0 就会得到 0=1。这体现了域上一元多项式情形与多元多项式情形的区别。
命名与历史背景
这一等式以法国数学家艾蒂安·贝祖的名字命名,他的研究包含了这一结论的多项式形式。整数形式的结论在他之前就已出现,并与古老的欧几里得算法密切相关。它不同于代数几何中的贝祖定理,后者讨论的是代数曲线的相交问题。