辗转相除法求函数逆元

辗转相除法求函数逆元是一种常用的方法。通过辗转相除法可以求出一个数的逆元，即使这个数和模数不互质。这种方法通常用于求解线性方程和求解欧拉定理中的逆元。

在C语言中，可以使用下述代码实现辗转相除法求函数逆元：

// 求逆元 a，m
int Inv_a(int a, int m) {
    int x, y;
    int d = exgcd(a, m, x, y);
    if (d == 1) {
        return (x % m + m) % m; // 保证逆元为正数
    } else {
        return -1; // ax + my = 1 不成立，即 a，m 不互质，无解
    }
}

其中，`exgcd`是扩展欧几里德算法，用于求解线性方程ax + my = 1中的解。

通过调用`Inv_a`函数，可以得到给定数a在模m下的逆元。

相关问题

辗转相除法求模乘逆元的c++代码

辗转相除法求模乘逆元的 C 代码如下：

#include <stdio.h>
int extgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main()
{
    int a = 3, m = 11;
    printf("%d 的模 %d 乘逆元为 %d\n", a, m, mod_inverse(a, m));
    return 0;
}

以上代码使用了扩展欧几里得算法求解模乘逆元。其中，`extgcd` 函数可以求解任意两个整数的最大公约数，并返回其值，同时通过引用返回参数 `x` 和 `y` 的值，满足 $ax + by = \gcd(a, b)$。`mod_inverse` 函数则使用 `extgcd` 求解模乘逆元，即 $a$ 模 $m$ 的乘法逆元 $x$，满足 $ax \equiv 1 \pmod m$，并返回其值。

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

下面是用辗转相除法求任意数的模乘逆元的 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 异常。