欧几里德算法求解一个方程，但有一个错误

Question

def kek(k,p):
    if k > p:
        return pew(k,p)
    elif k < p:
        return pew(p,k)
    else:
        return 1
def pew(j,k):
    if k == 0:
        return j,j,k
    q = j // k
    r = j % k
    R, h , o = pew(k,r)
    return R,o,h-q*o    
hmm = kek(231,1920)

'''
Math logic:
d = s x 231 + t x 1920
1920 = 8*231 + 72
231 = 3*72 + 15
72 = 4*15 + 12
15 = 1*12 + 3
12 = 4*3
d = gcd(231, 1920) = 3
3 = 15 – 12 
= 15 – (72 – 4*15) 
= 15 – 72 + 4*15 
= 5*15 – 72 
= 5*(231-3*72) – 72
= 5*231 – 15*72 – 72 
= 5*231 – 16*72 
= 5*231 – 16*(1920-8*231)
= 5*231 – 16*1920 + 128*231
= 133*231 – 16*1920 
= 133*231 + (-16)*1920
d = 3, s = 133 , t = -16
'''

然而，我得到-48的s和399的t和一个正确的结果3的d 我的递归方法有问题吗？上面的数学逻辑是你手工计算的，我用D=bR1+（a-Qb）R2和D=aR2+b*R3来实现我的复活召唤，但是它给了我133*3和-16*3的结果，这是我不想得到的。你知道吗

Answer 1

你的代码是很难遵循，但我想出了一个不同的解决方案，做同样的事情。你知道吗

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x

print(egcd(231, 1920)) # (3, 133, -16)