在数论中，裴蜀等式（）或貝祖定理（）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整數 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世纪初的法国数学家。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisants et délectables qui se font par les nombres）第二版中给出了问题的描述和证明。
然而，裴蜀推广了梅齐里亚克的结论，特别是探讨了多项式中的裴蜀等式，并给出了相应的定理和证明。
整数中的裴蜀定理
对任意两个整數a、b，设d是它们的最大公约数。那么关于未知数x和y的線性丟番圖方程（称为裴蜀等式）：
:\displaystyle ax+by=m
有整数解(x,y) 当且仅当m是d的整數倍。裴蜀等式有解时必然有无穷多个解。
证明：
如果 a 和 b 中有一个是0，比如a=0，那么它们两个的最大公约数是b。这时裴蜀等式变成\displaystyle by=m，它有整数解(x,y)当且仅当m是b的倍数，而且有解时必然有无穷多个解，因为x可以是任何整数。定理成立。
以下设a和 b都不为0。
设A = \{xa+yb; (x;y) \in \Z^2\}，下面证明A中的最小正元素是a与b的最大公约数。
首先，A \cap \N^ 不是空集（至少包含|a|和|b|），因此由于自然数集合是良序的，A中存在最小正元素d_0 = x_0a + y_0b。考虑A*中任意一个正元素p（=x_1a + y_1b）对d_0的带余除法：设p=qd_0+r，其中q为正整数，0 \le r 。但是
: r = p-qd_0 =x_1a + y_1b - q ( x_0a + y_0b)=(x_1 - qx_0)a + (y_1 - qy_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_0a + y_0b = ( x_0k + y_0l )d
因此d \ | \ d_0。所以d_0是a和b的最大公约数。
在方程ax+by=m中，如果 m= m_0 d_0，那么方程显然有无穷多个解：
:\left\{\left( m_0 x_0+\frac{kb}{d},\ m_0 y_0-\frac{ka}{d} \right) \mid k \in \mathbb{Z} \right\} 。
相反的，如果ax+by=m有整数解，那么|m| \in A，于是由前可知 d_0 \ | \ |m|（即 d_0 \ | \ m）。
m=1时，方程有解当且仅当a、b互质。方程有解时，解的集合是
: \left\{\left( \frac{m}{d} x_0+\frac{kb}{d},\ \frac{m}{d} y_0-\frac{ka}{d} \right) \mid k \in \mathbb{Z} \right\} 。其中(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。
:{\color{Blue}24x+31y=1 \rightarrow 1-31y=24x}
:{\color{Blue}\rightarrow 1-31y \equiv 0 \pmod{24} \rightarrow 1-(31-24)y \equiv 0 \pmod{24} \rightarrow 1-7y \equiv 0 \pmod{24}}
:{\color{Red}1-7y=24a \rightarrow 1-24a=7y}
:{\color{Red}\rightarrow 1-24a \equiv 0 \pmod{7} \rightarrow 1-(24-7 \times 3)a \equiv 0 \pmod{7} \rightarrow 1-3a \equiv 0 \pmod{7}}
:{\color{Green}1-3a=7b \rightarrow 1-7b=3a}
:{\color{Green}\rightarrow 1-7b \equiv 0 \pmod{3} \rightarrow 1-(7-3 \times 2)b \equiv 0 \pmod{3} \rightarrow 1-b \equiv 0 \pmod{3}}
:取b=1為滿足1-b \equiv 0 \pmod{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)為一組特解
于是通解为：\left\{ \left( 1 \cdot -9 + 31k, 1 \cdot 7-24k \right) | k \in \mathbb{Z} \right\}，即
: \left\{ \left( -9+31k, 7-24k \right) | k \in \mathbb{Z} \right\}。
多个整数间的裴蜀定理
设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]裡的多项式，裴蜀定理也成立。设有一族\mathbb{K}[X]裡的多项式\left(P_i\right)_{i\in I}。设\Delta为它们的最大公约式（首项系数为1且次数最高者），那么存在多项式\left(A_i\right)_{i\in I}使得\textstyle \Delta = \sum_{i\in I} A_iP_i。特别来说，如果\left(P_i\right)_{i\in I}互质（不是两两互质），那么存在多项式\left(A_i\right)_{i\in I}使得\textstyle \sum_{i\in I} A_iP_ = 1。
对于两个多项式的情况，与整数时一样可以得到通解。
任意主理想环上的情况
裴蜀可以推广到任意的主理想环上。设环A是主理想环，a和b为环中元素，d是它们的一个最大公约元，那么存在环中元素x和y使得：
ax + by = d
这是因为在主理想环中，a和b的最大公约元被定义为理想aA+bA的生成元。
参见
*理想 (环论)
*欧几里德整环
*欧几里德引理
*主理想环
*整除
参考来源
*闵嗣鹤、严士健，初等数论，高等教育出版社，2003。
*唐忠明，抽象代数基础，高等教育出版社，2006。
外部連結
评论 (0)