欧几里得算法求乘法逆元 python代码

设 x ∈ Z n , g c d ( x , y ) = 1 x\in \mathbb{Z}_n,gcd(x,y)=1 x∈Zn​,gcd(x,y)=1则 x x x在 Z n \mathbb{Z}_n Zn​上有乘法逆元。

对 x x x若存在 y y y使 x × y ≡ 1 m o d    n x\times y\equiv 1\mod n x×y≡1modn则 y y y为 x x x的乘法逆元。

python3.8

import numpy

def euclid(v1: int, v2: int) -> tuple:
    x = numpy.array([1, 0, v1])
    y = numpy.array([0, 1, v2])
    while True:
        if y[-1] == 0:
            return int(x[-1]), numpy.nan
        elif y[-1] == 1:
            return int(y[-1]), int((y[1]+v1) % v1)
        q = numpy.floor(x[-1]/y[-1])
        t = x - y*q
        x = y
        y = t

print('最大公约数：%s 乘法逆元：%s' % euclid(int(input()), int(input())))