c语言实现求乘法逆元

在C语言中，求乘法逆元通常是指对于两个整数a和n（其中a是n的一个非零倍数），找到一个整数x，使得a * x % n == 1。这种操作在模运算、加密算法（如RSA）等场景中有重要应用。下面是一个简单的实现，利用扩展欧几里得算法（也称为中国剩余定理的一种变形）：

#include <stdio.h>

// 扩展欧几里得算法求最大公约数和逆元
int extendedEuclid(int a, int b, int* x, int* y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int gcd = extendedEuclid(b, a % b, y, x);
    *y -= (a / b) * (*x);
    return gcd;
}

// 求解a mod n的逆元（如果存在）
int modInverse(int a, int n) {
    int x, y; // 存储结果
    int gcd = extendedEuclid(a, n, &x, &y); // 如果gcd不等于1，则a和n互质无逆元
    if (gcd != 1)
        return -1; // 无法找到逆元

    // 返回a的逆元，注意需要对n取模
    return (x % n + n) % n; // 把负数转换成正数
}

int main() {
    int a, n;
    printf("请输入a和n的值: ");
    scanf("%d %d", &a, &n);

    int inverse = modInverse(a, n);
    if (inverse != -1)
        printf("a关于n的逆元是: %d\n", inverse);
    else
        printf("a和n互质，不存在逆元.\n");

    return 0;
}

在这个代码中，`modInverse`函数首先计算a和n的最大公约数，然后根据扩展欧几里得算法的结果确定a的逆元。如果找不到逆元（即gcd不是1），则返回-1表示无法计算。