python求一个数模x的逆元y

可以使用扩展欧几里得算法来求解，具体步骤如下：

1. 定义函数 exgcd(a, b)，返回值为 (x, y, gcd(a, b))，其中 x 和 y 分别为扩展欧几里得算法中的系数。

2. 调用 exgcd(x, y)，得到 (a, b, gcd(x, y))。

3. 如果 gcd(x, y) 不等于 1，则 x 模 y 没有逆元。

4. 如果 gcd(x, y) 等于 1，则 a 就是 x 模 y 的逆元。

代码如下：

def exgcd(a, b):
    if b == :
        return (1, , a)
    x, y, gcd = exgcd(b, a % b)
    return (y, x - (a // b) * y, gcd)

x = int(input("请输入一个数 x："))
y = int(input("请输入模数 y："))

result = exgcd(x, y)
if result[2] != 1:
    print("x 模 y 没有逆元")
else:
    print("x 模 y 的逆元为：", result[])

注意：这里的代码只是一个示例，实际应用中需要对输入进行判断和异常处理。

相关问题

用Python求两个数的乘法逆元

乘法逆元指的是在模p下，对于给定的a和p，找到一个数x，使得a*x ≡ 1 (mod p)。下面是一个用Python求两个数的乘法逆元的示例代码：

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = gcd_extended(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

def find_inverse(a, p):
    gcd, x, y = gcd_extended(a, p)
    if gcd != 1:
        return None
    else:
        return (x % p + p) % p

a = 3
p = 11
inverse = find_inverse(a, p)
if inverse is None:
    print("No inverse exists")
else:
    print("Inverse of {} modulo {} is {}".format(a, p, inverse))

输出：

Inverse of 3 modulo 11 is 4

这里定义了一个求扩展欧几里得算法的函数`gcd_extended`，然后通过该函数求出a在模p下的逆元。如果a和p的最大公因数不为1，则不存在逆元，返回None。否则返回逆元。在上面的示例中，我们求解了3在模11下的逆元，结果为4。

写一个用辗转相除法求任意数的模乘逆元的代码

下面是用辗转相除法求任意数的模乘逆元的 Python 代码：

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = gcd_extended(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    gcd, x, y = gcd_extended(a, m)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return (x % m + m) % m

其中，`gcd_extended` 函数用于求解两个数的最大公因数和扩展欧几里得算法中的 x、y 值，`mod_inverse` 函数用于求解任意数的模乘逆元。如果模乘逆元不存在，则会抛出 ValueError 异常。