貝祖等式

在数论中，裴蜀等式（Template:Lang-en）或貝祖定理（Template:Lang）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整數 $a$、$b$ 和 $m$，关于未知数 $x$ 和 $y$ 的線性丟番圖方程（称为裴蜀等式）：

$ax+by=m$

有整数解时当且仅当 $m$ 是 $a$ 及 $b$ 的最大公约数 $d$ 的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 $x$、$y$ 都稱為裴蜀數，可用擴展歐幾里得演算法求得。

例如，12 和 42 的最大公因數是 6，则方程 $12x+42y=6$ 有解。事实上有 $(-3)\times 12+1\times 42=6$、$4\times 12+(-1)\times 42=6$等。

特别来说，方程 $ax+by=1$ 有整数解当且仅当整数 $a$ 和 $b$ 互素。

裴蜀等式也可以用来给最大公约数定义：$d$ 其實就是最小的可以寫成 $ax+by$ 形式的正整數。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。

历史

历史上首先证明关于整数的裴蜀定理的并不是裴蜀，而是17世纪初的法国数学家Template:Link-fr。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisants et délectables qui se font par les nombres）第二版中给出了问题的描述和证明。

然而，裴蜀推广了梅齐里亚克的结论，特别是探讨了多项式中的裴蜀等式，并给出了相应的定理和证明。

整数中的裴蜀定理

对任意两个整數$a$、$b$，设$d$是它们的最大公约数。那么关于未知数$x$和$y$的線性丟番圖方程（称为裴蜀等式）：

$ax+by=m$

有整数解$(x,y)$ 当且仅当$m$是$d$的整數倍。裴蜀等式有解时必然有无穷多个解。

证明：

如果 $a$ 和 $b$ 中有一个是0，比如$a=0$，那么它们两个的最大公约数是$b$。这时裴蜀等式变成$by=m$，它有整数解$(x,y)$当且仅当$m$是$b$的倍数，而且有解时必然有无穷多个解，因为$x$可以是任何整数。定理成立。

以下设$a$和 $b$都不为0。

设$A=\{xa+yb;(x;y)\in {\mathbb{Z}}^2\}$，下面证明$A$中的最小正元素是$a$与$b$的最大公约数。

首先，$A\cap {\mathbb{N}}^{*}$ 不是空集（至少包含$|a|$和$|b|$），因此由于自然数集合是良序的，$A$中存在最小正元素$d_0=x_{0}a+y_{0}b$。考虑$A$中任意一个正元素$p$（$=x_{1}a+y_{1}b$）对$d_0$的带余除法：设$p=q{d}_0+r$，其中$q$为正整数，$0\le r<d_0$。但是

$r=p-q{d}_0=x_{1}a+y_{1}b-q(x_{0}a+y_{0}b)=(x_1-q{x}_0)a+(y_1-q{y}_0)b\in A$

因此 $r=0$，$d_0|p$。也就是说，$A$中任意一个正元素$p$都是 $d_0$ 的倍数，特别地：$d_0|a$、$d_0|b$。因此 $d_0$ 是$a$和$b$的公约数。

另一方面，对$a$和$b$的任意正公约数$d$，设$a=kd$、 $b=ld$，那么

$d_0=x_{0}a+y_{0}b=(x_{0}k+y_{0}l)d$

因此$d|d_0$。所以$d_0$是$a$和$b$的最大公约数。

在方程$ax+by=m$中，如果 $m=m_0{d}_0$，那么方程显然有无穷多个解：

$\{(m_0{x}_0+\frac{kb}{d},m_0{y}_0-\frac{ka}{d})\mid k\in \mathbb{Z}\}$。

相反的，如果$ax+by=m$有整数解，那么$|m|\in A$，于是由前可知 $d_0||m|$（即 $d_0|m$）。

$m=1$时，方程有解当且仅当$a$、$b$互质。方程有解时，解的集合是

$\{(\frac{m}{d}{x}_0+\frac{kb}{d},\frac{m}{d}{y}_0-\frac{ka}{d})\mid k\in \mathbb{Z}\}$。其中$(x_0,y_0)$是方程$ax+by=d$的一个解，可由辗转相除法得到。

所有解中，恰有二解$(x,y)$满足$|x|\le |b/d|$及$|y|\le |a/d|$，等號只會在$a$及$b$其中一個是另一個的倍數時成立。輾轉相除法給出的解會是這兩解中的一個。

例子

丟番圖方程$504x+651y=14$ 没有整数解，因为504和651的最大公约数是21。而方程$504x+651y=21$是有解的。为了求出通解，可以先约掉公约数21，这样得到方程：

$24x+31y=1$。

通过扩展欧几里得算法可以得到一组特解$(x,y)=(-9,7)$：$24\cdot (-9)+31\cdot 7=-216+217=1$。 Template:HideH

$24x+31y=1\to 1-31y=24x$

$\to 1-31y\equiv 0(\mathrm{mod}24)\to 1-(31-24)y\equiv 0(\mathrm{mod}24)\to 1-7y\equiv 0(\mathrm{mod}24)$

Template:Red$1-7y=24a\to 1-24a=7y$

$\to 1-24a\equiv 0(\mathrm{mod}7)\to 1-(24-7\times 3)a\equiv 0(\mathrm{mod}7)\to 1-3a\equiv 0(\mathrm{mod}7)$

Template:Green$1-3a=7b\to 1-7b=3a$

$\to 1-7b\equiv 0(\mathrm{mod}3)\to 1-(7-3\times 2)b\equiv 0(\mathrm{mod}3)\to 1-b\equiv 0(\mathrm{mod}3)$

取$b=1$為滿足$1-b\equiv 0(\mathrm{mod}3)$的解

---

將$b=1$代回$1-3a=7b$，解一元一次方程式得$a=-2$

將$a=-2$代回$1-7y=24a$，得$y=7$

將$y=7$代回$24x+31y=1$，得$x=-9$

故$(x,y)=(-9,7)$為一組特解

Template:HideF 于是通解为：$\{(1\cdot -9+31k,1\cdot 7-24k)|k\in \mathbb{Z}\}$，即

$\{(-9+31k,7-24k)|k\in \mathbb{Z}\}$。

多个整数间的裴蜀定理

设$a_1,\cdots a_n$为$n$个整数，$d$是它们的最大公约数，那么存在整数$x_1,\cdots x_n$ 使得 $x_1\cdot a_1+\cdots x_n\cdot a_n=d$。特别来说，如果$a_1,\cdots a_n$互质（不是两两互质），那么存在整数$x_1,\cdots x_n$ 使得 $x_1\cdot a_1+\cdots x_n\cdot a_n=1$。

多项式环$K[X]$裡的貝祖定理

$K$为域时，对于多项式环$K[X]$裡的多项式，裴蜀定理也成立。设有一族$𝕂[X]$裡的多项式${\left(P_i\right)}_{i\in I}$。设$\mathrm{\Delta }$为它们的最大公约式（首项系数为1且次数最高者），那么存在多项式${\left(A_i\right)}_{i\in I}$使得$\mathrm{\Delta }=\sum _{i\in I}{A}_i{P}_i$。特别来说，如果${\left(P_i\right)}_{i\in I}$互质（不是两两互质），那么存在多项式${\left(A_i\right)}_{i\in I}$使得$\sum _{i\in I}{A}_i{P}_{=}1$。

对于两个多项式的情况，与整数时一样可以得到通解。

任意主理想环上的情况

裴蜀可以推广到任意的主理想环上。设环$A$是主理想环，$a$和$b$为环中元素，$d$是它们的一个最大公约元，那么存在环中元素$x$和$y$使得：

$ax+by=d$

这是因为在主理想环中，$a$和$b$的最大公约元被定义为理想$aA+bA$的生成元。

参见

• 理想 (环论)
• 欧几里德整环
• 欧几里德引理
• 主理想环
• 整除

参考来源

• 闵嗣鹤、严士健，初等数论，高等教育出版社，2003。
• 唐忠明，抽象代数基础，高等教育出版社，2006。

外部連結

• 線上計算器 Template:Wayback