使用推广Euclid算法求67模119的逆元

首先，我们使用Euclid算法来求出67和119的最大公约数：

119 = 1 * 67 + 52 67 = 1 * 52 + 15 52 = 3 * 15 + 7 15 = 2 * 7 + 1

最后一行的余数1是我们需要的。现在，我们倒着回去，使用Euclid扩展算法来求出1的系数：

1 = 15 - 2 * 7 = 15 - 2 * (52 - 3 * 15) = 7 * 15 - 2 * 52 = 7 * (67 - 1 * 52) - 2 * 52 = 7 * 67 - 9 * 52 = 7 * 67 - 9 * (119 - 1 * 67) = 16 * 67 - 9 * 119

因此，67模119的逆元为16。