数论——贝祖定理证明及代码实现

首先，引入贝祖定理的定义：

裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

证明：

我们首先需要找出a和b的 gcd（a，b），在求解 gcd（a，b）时，可用欧几里得算法（辗转相除法）对此进行求解：

a=eval(input())
b=eval(input())
if a<b:
    t=a
    a=b
    b=t
    
a1=a
b1=b

while a%b!=0:  #判断a%b是否存在余数
    temp=a%b
    a=b
    b=temp 
    
print(b)

一、在求出a和b的最大公约数后，我们便得知d的数值。接下来，我们先讨论 a*x+b*y=k*d的问题

由于我们已经知道：

a % d == 0

b % d == 0

所以我们设a=k1*d ; b=k2*d,于是原式等同于 k1*d*x+k2*d*y=k*d,消去d，当k=k1*x+k2*y时即满足条件，由于5个值都为变量，可以认为设定成立，原式得证。

二、我们求证ax+by=d成立

由于a=k1*d ; b=k2*d，所以k1*d*x+k2*d*y=d，消去d，即得到k1*x+k2*y=1

其中 k1=a/d

        k2=b/d

此两数我们都可以解出，于是，我使用暴力法求解：在循环中，i++，当（i*k1）//k2==1时，跳出循环并输出

代码：

a=a1/b
b=b1/b
if b==1:#需要考虑是否第二个就为a和b的最大公约数
    i=1
    m=a-1
else:
    i=1
    while i:
        if (i*a)%b==1:#暴力求解正确的x值和y值
            break
        i=i+1
    m=(i*a)//b
print(i)
print(-m) #由于第一个代码中已经将a，b从大到小排列，所以第一个值必为正，第二个值必为负

最终总代码为：

import gmpy2

a=eval(input())
b=eval(input())
if a<b:
    t=a
    a=b
    b=t
    
a1=a
b1=b

while a%b!=0:
    temp=a%b
    a=b
    b=temp 
    
print(b)
a=a1/b
b=b1/b
if b==1:
    i=1
    m=a-1
else:
    i=1
    while i:
        if (i*a)%b==1:
            break
        i=i+1
    m=(i*a)//b
print(i)
print(-m)