c语言编程辗转相除法求乘法逆元

你可以使用辗转相除法来计算乘法逆元。乘法逆元是指在模运算中，对于给定的整数a和模数m，找到一个整数b，使得(a * b) % m = 1。下面是使用C语言编写的辗转相除法求乘法逆元的示例代码：

#include <stdio.h>

int extendedEuclidean(int a, int b, int *x, int *y) {
    // 基本情况：当b为0时，设置x和y为1和0，并返回a
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    
    // 递归计算扩展欧几里德算法
    int x1, y1;
    int gcd = extendedEuclidean(b, a % b, &x1, &y1);
    
    // 更新x和y的值
    *x = y1;
    *y = x1 - (a / b) * y1;
    
    return gcd;
}

int multiplicativeInverse(int a, int m) {
    int x, y;
    int gcd = extendedEuclidean(a, m, &x, &y);
    
    // 如果a和m不互质，则不存在乘法逆元
    if (gcd != 1) {
        printf("乘法逆元不存在！\n");
        return -1;
    }
    
    // 计算正数形式的乘法逆元
    int inverse = (x % m + m) % m;
    
    return inverse;
}

int main() {
    int a, m;
    printf("请输入整数a和模数m：");
    scanf("%d %d", &a, &m);
    
    int inverse = multiplicativeInverse(a, m);
    
    if (inverse != -1) {
        printf("乘法逆元：%d\n", inverse);
    }
    
    return 0;
}

你可以通过输入一个整数a和模数m来执行该程序。程序将输出计算得到的乘法逆元。如果乘法逆元不存在，则会打印“乘法逆元不存在！”的提示信息。

请注意，这段代码中没有对输入进行有效性验证，你可能需要自行添加适当的错误处理部分。