用c实现编程计算同余组｛x ≡b1（mod m1）x ≡b2（mod m2）的解

#include <stdio.h>

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

// 计算扩展欧几里得算法
int extendedGcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
} else {
int gcd = extendedGcd(b, a % b, x, y);
int temp = *x;
*x = *y;
*y = temp - (a / b) * (*y);
return gcd;
}
}

// 计算同余方程组的解
void modularEquations(int b1, int m1, int b2, int m2) {
int d = gcd(m1, m2);
if ((b2 - b1) % d != 0) {
printf("该同余方程组无解\n");
return;
}
int x, y;
int m = m1 / d * m2; // 计算最小公倍数
extendedGcd(m1, m2, &x, &y);
int t = (b2 - b1) / d * x % (m2 / d);
int x0 = (b1 + m1 * t) % m;
printf("该同余方程组的解为: x ≡ %d（mod %d）\n", x0, m);
}

int main() {
modularEquations(2, 5, 3, 7);
modularEquations(2, 5, 3, 6);
return 0;
}