c语言扩展欧几里得算法求逆元

扩展欧几里得算法可以用来求解线性同余方程的解，从而求解模的逆元。以下是用C语言实现的扩展欧几里得算法：

#include <stdio.h>

int gcdExtended(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }

    int x1, y1;
    int gcd = gcdExtended(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}

int modInverse(int a, int m) {
    int x, y;
    int gcd = gcdExtended(a, m, &x, &y);

    if (gcd != 1) {
        printf("Inverse doesn't exist\n");
        return -1;
    } else {
        int res = (x % m + m) % m;
        return res;
    }
}

int main() {
    int a = 5, m = 11;
    int inv = modInverse(a, m);

    if (inv == -1) {
        printf("No inverse exists\n");
    } else {
        printf("Inverse of %d mod %d is %d\n", a, m, inv);
    }

    return 0;
}

在这个例子中，我们要求解 5 在模 11 下的逆元，即 $5^{-1} \bmod 11$。运行程序后，输出结果为：

Inverse of 5 mod 11 is 9

因此，$5^{-1} \bmod 11 = 9$。