• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

在数论中,佩-舒方程(英文:Bzout恒等式)或Bzout引理是关于最大公约数(或最大公约数公式)的定理。佩-舒定理以法国数学家艾蒂安佩-舒的名字命名,它解释了关于未知数X和Y对于任意整数A、B及其最大公约数D的线性丢番图方程(称为佩-舒方程):

Ax=m有整数解当且仅当m是d的倍数。

裴树方程有解时,必然有无穷多个整数解。每一组解x和y都称为Pei-Shu数,可以通过扩展的欧几里得算法得到。

例如,如果12和42的最大公因数是6,那么等式12x 42y=6就有解。其实还有(-3)12 142=6和412 (-1)42=6。

特别地,当且仅当整数a和b互质时,方程ax by=1有整数解。

裴方程也可以用来定义最大公约数:D实际上是最小的正整数,可以写成ax的形式。(这个定义的本质是整个环中的“理想”概念。因此,对于多项式整环,也有相应的裴树定理。)

证明:

如果

比如和中有一个是0,那么它们的最大公约数就是。这时佩树方程就变成了它有整数解(x,y)当且仅当它是的倍数,有解的时候一定有无穷多个解,因为它可以是任意整数。这个定理成立。

设a和b不为0。

假设证明A中最小的正元素是A和b的最大公约数。

首先,它不是一个空集(至少包括和),所以因为自然数集是有序的,所以有最小的正元素在里面。请考虑:let中任意正元素对的余数除法,其中是正整数。但是

它已经是集合中最小的正元素了,所以。

因此。也就是说,A中任何一个正元素p都是的倍数,尤其是:因此,它是和的公约数。

另一方面,对于A和B的任何正的公约数,设,那么

因此。所以是和的最大公约数。

在方程中,如果,那么方程显然有无穷多个解:

i4nawbrcdts5195.png

相反,如果有整数解,那么从前面就可以知道(也就是)。

当m=1时,方程有解当且仅当A和B互质。当方程有解时,解集为

yzjzfjuepd35196.png

其中是方程ax by=d的解,可通过相间除法获得。

在所有解中,只有一个解(x,y)得到满足。

培树方程为扩展欧几里得铺平了道路

Link to comment
Share on other sites