裴蜀定理

历史

历史上首先证明关于整数的裴蜀定理的并不是裴蜀，而是17世纪初的法国数学家克劳德-加斯帕·巴歇·德·梅齐里亚克（Claude-Gaspard Bachet de Méziriac）。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisans et délectables qui se font par les nombres）第二版中给出了问题的描述和证明。

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

整数中的裴蜀定理

对任意两个整数a{\displaystyle a}、b{\displaystyle b}，设d{\displaystyle d}是它们的最大公约数。那么关于未知数x{\displaystyle x}和y{\displaystyle y}的线性丢番图方程（称为裴蜀等式）：

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

证明：如果 a{\displaystyle a} 和 b{\displaystyle b} 中有一个是0，比如a=0{\displaystyle a=0}，那么它们两个的最大公约数是b{\displaystyle b}。这时裴蜀等式变成by=m{\displaystyle \displaystyle by=m}，它有整数解(x,y) 当且仅当m 是d 的倍数，而且有解时必然有无穷多个解，因为x{\displaystyle x} 可以是任何整数。定理成立。以下设 a{\displaystyle a}和 b{\displaystyle b} 都不为0。设A={xa+yb;(x;y)∈ ∈ -->Z2}{\displaystyle A=\{xa+yb;(x;y)\in \mathbb {Z} ^{2}\}}，下面证明A{\displaystyle A}中的最小正元素是 a{\displaystyle a} 与 b{\displaystyle b} 的最大公约数。首先，A∩ ∩ -->N∗ ∗ -->{\displaystyle A\cap \mathbb {N}空集{*}} 不是空集（至少包含|a|{\displaystyle |a|} 和|b|{\displaystyle |b|}），因此由于自然数集合是良序的， A{\displaystyle A} 中存在最小正元素d0=x0a+y0b{\displaystyle d_{0}=x_{0}a+y_{0}b}。考虑A中任意一个正元素p（=x1a+y1b{\displaystyle =x_{1}a+y_{1}b}）对 d0{\displaystyle d_{0}} 的带余除法：设p=qd0+r{\displaystyle p=qd_{0}+r}，其中q 为正整数，0≤ ≤ -->rqd0=x1a+y1b− − -->q(x0a+y0b)∈ ∈ -->A{\displaystyle r=p-qd_{0}=x_{1}a+y_{1}b-q(x_{0}a+y_{0}b)\in A}因此 r=0{\displaystyle r=0}，d0 | p{\displaystyle d_{0}\ |\ p}。也就是说，A中任意一个正元素p都是 d0{\displaystyle d_{0}} 的倍数，特别地：d0 | a{\displaystyle d_{0}\ |\ a}、d0 | b{\displaystyle d_{0}\ |\ b}。因此 d0{\displaystyle d_{0}} 是 a{\displaystyle a} 和 b{\displaystyle b} 的公约数。另一方面，对 a{\displaystyle a} 和 b{\displaystyle b} 的任意正公约数d{\displaystyle d}，设 a=kd{\displaystyle a=kd}、 b=ld{\displaystyle b=ld}，那么d0=x0a+y0b=(x0k+y0l)d{\displaystyle d_{0}=x_{0}a+y_{0}b=(x_{0}k+y_{0}l)d}因此 d | d0{\displaystyle d\ |\ d_{0}}。所以 d0{\displaystyle d_{0}} 是 a{\displaystyle a} 和 b{\displaystyle b} 的最大公约数。在方程ax+by=m{\displaystyle ax+by=m}中，如果 m=m0d0{\displaystyle m=m_{0}d_{0}}，那么方程显然有无穷多个解：{(m0x0+kbd, m0y0− − -->kad)∣ ∣ -->k∈ ∈ -->Z}{\displaystyle \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{\displaystyle ax+by=m}有整数解，那么 |m|∈ ∈ -->A{\displaystyle |m|\in A}，于是由前可知 d0 | |m|{\displaystyle d_{0}\ |\ |m|}（即 d0 | m{\displaystyle d_{0}\ |\ m}）。

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

所有解中，有且仅有一个解(x,y) 满足− − -->b≤ ≤ -->x≤ ≤ -->b{\displaystyle -b\leq x\leq b}，− − -->a≤ ≤ -->y≤ ≤ -->a{\displaystyle -a\leq y\leq a}。

例子

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

通过扩展欧几里得算法可以得到一组解(− − -->9,7){\displaystyle (-9,7)}：24⋅ ⋅ -->(− − -->9)+31⋅ ⋅ -->7=− − -->216+217=1{\displaystyle 24\cdot (-9)+31\cdot 7=-216+217=1}。

于是通解为：{(1⋅ ⋅ -->− − -->9+31k,1⋅ ⋅ -->7− − -->24k)|k∈ ∈ -->Z}{\displaystyle \left\{\left(1\cdot -9+31k,1\cdot 7-24k\right)|k\in \mathbb {Z} \right\}}，即

多个整数间的裴蜀定理

设a1,⋯ ⋯ -->an{\displaystyle a_{1},\cdots a_{n}}为n个整数，d{\displaystyle d}是它们的最大公约数，那么存在整数x1,⋯ ⋯ -->xn{\displaystyle x_{1},\cdots x_{n}} 使得 x1⋅ ⋅ -->a1+⋯ ⋯ -->xn⋅ ⋅ -->an=d{\displaystyle x_{1}\cdot a_{1}+\cdots x_{n}\cdot a_{n}=d}。特别来说，如果a1,⋯ ⋯ -->an{\displaystyle a_{1},\cdots a_{n}}互质（不是两两互质），那么存在整数x1,⋯ ⋯ -->xn{\displaystyle x_{1},\cdots x_{n}} 使得 x1⋅ ⋅ -->a1+⋯ ⋯ -->xn⋅ ⋅ -->an=1{\displaystyle x_{1}\cdot a_{1}+\cdots x_{n}\cdot a_{n}=1}。

多项式环K[X]里的裴蜀定理

K为域时，对于多项式环K[X]里的多项式，裴蜀定理也成立。设有一族K[X]{\displaystyle \mathbb {K} [X]}里的多项式(Pi)i∈ ∈ -->I{\displaystyle \left(P_{i}\right)_{i\in I}}。设Δ Δ -->{\displaystyle \Delta }为它们的最大公约式（首项系数为1且次数最高者），那么存在多项式(Ai)i∈ ∈ -->I{\displaystyle \left(A_{i}\right)_{i\in I}}使得Δ Δ -->=∑ ∑ -->i∈ ∈ -->IAiPi{\displaystyle \textstyle \Delta =\sum _{i\in I}A_{i}P_{i}}。特别来说，如果(Pi)i∈ ∈ -->I{\displaystyle \left(P_{i}\right)_{i\in I}}互质（不是两两互质），那么存在多项式(Ai)i∈ ∈ -->I{\displaystyle \left(A_{i}\right)_{i\in I}}使得∑ ∑ -->i∈ ∈ -->IAiP=1{\displaystyle \textstyle \sum _{i\in I}A_{i}P_{=}1}。

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

任意主理想环上的情况

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

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

参见

理想 (环论)

欧几里德整环

欧几里德引理

主理想环

整除

参考来源

闵嗣鹤、严士健，初等数论，高等教育出版社，2003。

唐忠明，抽象代数基础，高等教育出版社，2006。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。