貝祖等式

维基百科,自由的百科全书
跳转至: 导航搜索

数论中,裴蜀等式貝祖定理是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整數ab和它们的最大公约数d,关于未知数xy線性丟番圖方程(称为裴蜀等式):

ax+by=m

有整数解时当且仅当md倍数。裴蜀等式有解时必然有无穷多个整数解,每组解xy都稱為裴蜀數,可用擴展歐幾里得演算法求得。

例如,12和42的最大公因數是6,则方程12x+42y=6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。

特别来说,方程 ax+by=1 有整数解当且仅当整数ab互素

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

历史[编辑]

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

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

整数中的裴蜀定理[编辑]

对任意两个整數ab,设d是它们的最大公约数。那么关于未知数xy線性丟番圖方程(称为裴蜀等式):

\displaystyle ax+by=m

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

证明

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

以下设 ab 都不为0。

A = \{xa+yb; (x;y) \in \Z^2\},下面证明A中的最小正元素是 ab 的最大公约数。

首先,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 < d_0。但是

r = p-qd_0 =x_1a + y_1b - q ( x_0a + y_0b) \in A

因此 r=0d_0 \ | \ p。也就是说,A中任意一个正元素p都是 d_0 的倍数,特别地:d_0 \ | \ ad_0 \ | \ b。因此 d_0ab公约数

另一方面,对 ab 的任意正公约数d,设 a=kdb=ld,那么

d_0 =x_0a + y_0b = ( x_0k + y_0l )d

因此 d \ | \ d_0。所以 d_0ab最大公约数

在方程ax+by=m中,如果  m= m_0 d_0,那么方程显然有无穷多个解:

\left\{\left( m_0 \left(x_0+\frac{kb}{d}\right),\ m_0 \left( y_0-\frac{ka}{d}\right) \right) \mid k \in \mathbb{Z} \right\}

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

m=1时,方程有解当且仅当ab互质。方程有解时,解的集合是

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

所有解中,有且仅有一个解(x,y) 满足-b \le x \le b-a \le y \le a

例子[编辑]

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

24x+31y=1

通过扩展欧几里得算法可以得到一组解(-9,7)24 \cdot (-9) + 31 \cdot 7=-216 + 217 = 1

于是通解为:\left\{ \left( 21 \left( -9 + 31k \right), 21 \left(7-24k \right) \right) | k \in \mathbb{Z} \right\},即

\left\{ \left( -189+651k, 147-504k \right) | k \in \mathbb{Z} \right\}

多个整数间的裴蜀定理[编辑]

a_1, \cdots a_nn个整数,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是主理想环,ab 为环中元素,d是它们的一个最大公约元,那么存在环中元素xy使得:

ax + by = d

这是因为在主理想环中,ab的最大公约元被定义为理想aA+bA生成元

参见[编辑]

参考来源[编辑]

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

外部鏈結[编辑]