C求解a在模b下的逆元

要求解a在模b下的逆元，可以使用扩展欧几里得算法。具体步骤如下：

1. 首先求出a和b的最大公约数gcd(a,b)，如果gcd(a,b)不为1，则a在模b下不存在逆元。

2. 使用扩展欧几里得算法求出a和b的最大公约数gcd(a,b)以及一组解x和y，使得ax+by=gcd(a,b)。

3. 如果gcd(a,b)=1，则a在模b下的逆元为x，即a在模b下的逆元为a关于模b的乘法逆元是x(mod b)。

因此，可以通过以下代码来求解a在模b下的逆元：

int ext_gcd(int a, int b, int *x, int *y){
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }
    int r = ext_gcd(b, a % b, x, y);
    int t = *x;
    *x = *y;
    *y = t - a / b * (*y);
    return r;
}

int mod_inverse(int a, int b){
    int x, y;
    int d = ext_gcd(a, b, &x, &y);
    if(d == 1){
        return (x % b + b) % b;
    }
    return -1;
}

其中，ext_gcd函数用于求解a和b的最大公约数以及一组解x和y，而mod_inverse函数则用于判断是否存在逆元，如果存在则返回a在模b下的逆元。

相关问题

C语言求解a在模b下的逆元

要求a在模b下的逆元，可以使用扩展欧几里得算法求解。具体步骤如下：

1. 首先判断a和b是否互质，如果不互质，则a在模b下不存在逆元。

2. 使用扩展欧几里得算法求解a和b的最大公约数gcd，以及x和y的值，使得ax+by=gcd(a,b)。

3. 如果gcd(a,b)不等于1，则a在模b下不存在逆元。

4. 如果gcd(a,b)等于1，则a在模b下的逆元为x mod b。

下面是C语言代码实现：

#include <stdio.h>

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

int mod_inverse(int a, int b)
{
    int x, y;
    int gcd = ext_gcd(a, b, &x, &y);
    if (gcd != 1) {
        printf("Error: %d is not invertible mod %d.\n", a, b);
        return -1;
    }
    return (x % b + b) % b;
}

int main()
{
    int a = 3, b = 7;
    int inverse = mod_inverse(a, b);
    printf("%d's inverse mod %d is %d.\n", a, b, inverse);
    return 0;
}

输出：

3's inverse mod 7 is 5.

注意，扩展欧几里得算法中x和y的值可能为负数，需要进行调整，使得x mod b为正数。

C求解a在模b下的逆元举例子

好的，假设我们要求解在模7下，a=3的逆元，也就是找到一个整数x，使得3x ≡ 1 (mod 7)。我们可以使用扩展欧几里得算法来解决这个问题。

首先，我们列出扩展欧几里得算法的基本式子：

对于任意两个整数a,b，扩展欧几里得算法返回它们的最大公约数gcd(a,b)以及一组整数x和y，满足ax + by = gcd(a,b)。

我们将a=3，b=7代入上面的式子中，得到：

gcd(3,7) = 1 = (-2) * 3 + 1 * 7

这说明3和7的最大公约数是1，而且存在一组整数x和y，满足-2 * 3 + 1 * 7 = 1。

因此，我们可以得到3的逆元为-2，但是因为负数在模7下没有意义，所以我们需要将-2转化为一个在模7下的正整数：

-2 ≡ 5 (mod 7)

因此，3在模7下的逆元为5。

总结一下，求解a在模b下的逆元的步骤是：

1. 使用扩展欧几里得算法求解a和b的最大公约数gcd(a,b)以及一组整数x和y，满足ax + by = gcd(a,b)。

2. 如果gcd(a,b)不等于1，则a在模b下没有逆元。

3. 如果gcd(a,b)等于1，则a在模b下的逆元为x（如果x是负数，则加上b直到x成为一个正整数）。