用推广的euclid算法求67mod119的逆元

欧几里得算法（Euclid's algorithm）是一种计算最大公约数（Greatest Common Divisor，GCD）的方法。根据欧几里得算法的扩展版本，可以计算两个数的乘法逆元。

要求一个数的乘法逆元，可以使用扩展欧几里得算法。扩展欧几里得算法可以用来计算贝祖等式（Bézout's identity）的解，而乘法逆元就是贝祖等式的解之一。

对于两个整数a和b，a的乘法逆元是指一个整数x，满足以下条件： ax ≡ 1 (mod b)

我们要求的是67在模119下的乘法逆元，即67的逆元。以下是使用扩展欧几里得算法来计算67在模119下的乘法逆元的过程：

初始化变量： a = 119 b = 67 x1 = 0 x2 = 1 y1 = 1 y2 = 0
开始循环直到b为0：
- 计算商：q = a // b
- 更新a：a, b = b, a % b
- 更新x和y：x1, x2 = x2 - q * x1, x1 y1, y2 = y2 - q * y1, y1
当b为0时，停止循环。此时a的值就是67和119的最大公约数，同时x2和y2就是67在模119下的乘法逆元。

根据上述步骤，我们可以计算出67在模119下的乘法逆元为77