用欧几里得算法求乘法逆元，不要使用循环。用c语言实现

欧几里得算法通常用于找到两个整数的最大公约数（GCD），而利用这个算法也可以找到它们之间的最小公倍数（LCM），进而得到其中一个整数（比如a）的乘法逆元，即存在另一个整数b使得ab模n等于1（其中n是除数）。这里是一个不使用循环的递归版本的C语言实现：

#include <stdio.h>

// 辅助函数：计算最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 主函数：计算乘法逆元
int modInverse(int a, int n) {
    // 根据欧几里得算法，如果gcd(a, n) = 1，则a对n有逆元
    if (gcd(a, n) != 1)
        return -1; // 如果没有逆元，返回-1

    // 计算逆元，利用公式 inv(a, n) = a^(n-2) mod n
    int m = n - 2, x = 0, y = 1;
    while (m > 0) {
        int q = a / m;
        int t = x;
        x = y - q * x;
        y = t;
        a %= m;
        m = a;
    }
    return (x + n) % n; // 返回逆元
}

int main() {
    int a, n;
    printf("请输入一个正整数a和它的模n（n>1）：");
    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;
}