用c++ 两个非负整数m,b,且m>b,求b在Z_m^*中的乘法逆元，其中m>100,b>10

可以使用扩展欧几里得算法求解b在Z_m^*中的乘法逆元。

首先，我们需要判断b和m是否互质。如果它们不互质，则b在Z_m^*中不存在乘法逆元。可以使用辗转相除法判断它们是否互质。

接下来，我们可以使用扩展欧几里得算法求解b在Z_m^*中的乘法逆元。

假设x是b在Z_m^*中的乘法逆元，则有以下等式成立：

b * x ≡ 1 (mod m)

根据扩展欧几里得算法的原理，我们可以得到以下递归式：

gcd(b, m) = gcd(m, b % m)
a = x2
x2 = x1 - (b / m) * x2
x1 = a

其中，gcd(b, m)表示b和m的最大公约数，x1和x2是扩展欧几里得算法中求解的两个系数。

最终，当gcd(b, m)等于1时，x2即为b在Z_m^*中的乘法逆元。

下面是C++代码实现：

#include <iostream>

using namespace std;

int extgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

int mod(int a, int m)
{
    return (a % m + m) % m;
}

int modInverse(int b, int m)
{
    int x, y;
    int gcd = extgcd(b, m, x, y);
    if (gcd != 1)
    {
        cout << "Error: " << b << " is not invertible modulo " << m << endl;
        return -1;
    }
    return mod(x, m);
}

int main()
{
    int m = 101; // m > 100
    int b = 11; // b > 10 and b < m
    int inv = modInverse(b, m);
    if (inv != -1)
    {
        cout << "The inverse of " << b << " modulo " << m << " is " << inv << endl;
    }
    return 0;
}