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

扩展欧几里得算法可以求解两个数的最大公约数以及一个数在模意义下的逆元。下面是求解一个数在模意义下的逆元的C语言代码：

#include <stdio.h>

// 扩展欧几里得算法求解 ax + by = gcd(a, b) 的一组可行解 (x, y)
int exgcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, x, y);
    int tmp = *x;
    *x = *y;
    *y = tmp - a / b * (*y);
    return gcd;
}

// 求解 a 在模意义下的逆元，即 a * x ≡ 1 (mod m)
int inverse(int a, int m) {
    int x, y;
    int gcd = exgcd(a, m, &x, &y);
    if (gcd != 1) {
        return -1;  // 不存在逆元
    }
    return (x % m + m) % m;
}

int main() {
    int a = 3, m = 11;
    int inv = inverse(a, m);
    if (inv == -1) {
        printf("%d 没有逆元\n", a);
    } else {
        printf("%d 在模 %d 意义下的逆元是 %d\n", a, m, inv);
    }
    return 0;
}

其中，`exgcd` 函数用于求解一组可行解 (x, y)，即 ax + by = gcd(a, b)，这里用到了递归的思想。最后，我们可以利用一组可行解和贝祖定理，求解 a 在模意义下的逆元。如果不存在逆元，函数返回 -1。