用C语言实现扩展的欧几里得算法， 计算8787 (mod 91919)的乘法逆元素

在C语言中，扩展欧几里得算法（Extended Euclidean Algorithm）可以用来找到两个大整数的最大公约数（GCD），同时还能求出其中一个数对于另一个数的模反元素。下面是一个简单的C程序示例，用于计算8787除以91919的模逆元：

#include <stdio.h>

// 定义扩展欧几里德函数
int extended_euclidean(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a; // a就是最大公约数，x就是a对b的模逆元
    }
    int x1, y1;
    int gcd = extended_euclidean(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

int main() {
    int num1 = 8787;
    int num2 = 91919;

    int inverse;
    extended_euclidean(num2, num1, &inverse, NULL); // 计算num1对num2的模逆

    printf("8787 对于 91919 的模逆元是：%d\n", inverse);

    // 检查是否真的互为模逆（验证）
    if ((inverse * num1) % num2 == 1)
        printf("验证通过：(8787 * %d) % 91919 = 1\n", inverse);
    else
        printf("验证失败：(8787 * %d) % 91919 ≠ 1\n", inverse);

    return 0;
}

当你运行这个程序，它会计算并打印出8787对91919的模逆元，并通过乘法检查其结果是否满足互为模逆的关系。