编程实现计算同余式组x≡b1(mod m1) x≡b2(mod m2)的解的算法

1. 判断m1和m2是否互质，如果不互质则无解。
2. 求出m1和m2的最大公约数gcd(m1, m2)，并判断b1和b2的差值是否能够被gcd(m1, m2)整除，如果不可整除则无解。
3. 求出m1和m2的扩展欧几里得算法解，即求出一组整数x和y，使得mx+ny=gcd(m1, m2)。这里可以使用扩展欧几里得算法求解。
4. 求出同余方程组的解x0 = b1 + m1*(b2 - b1)*x，其中x为任意整数。
5. 将x0带入同余方程组中检验是否满足要求，即x0 mod m1 = b1 和 x0 mod m2 = b2。
6. 如果x0不满足要求，则继续求解下一个解x0 + lcm(m1, m2)，其中lcm(m1, m2)为m1和m2的最小公倍数。
7. 重复步骤5和步骤6，直到找到满足要求的解为止。

相关问题

用C语言编程实现计算同余式组x≡b1(mod m1),x≡≡b2(mod m2)的解

#include <stdio.h>

int main()
{
int b1, m1, b2, m2;
printf("请输入同余式组x≡b1(mod m1),x≡b2(mod m2)的参数：\n");
printf("b1 = ");
scanf("%d", &b1);
printf("m1 = ");
scanf("%d", &m1);
printf("b2 = ");
scanf("%d", &b2);
printf("m2 = ");
scanf("%d", &m2);

int M1 = m1, M2 = m2;
int y1 = 1, y2 = 0;
while (m1 != 1)
{
int q = m1 / m2;
int t = m2;
m2 = m1 % m2;
m1 = t;
t = y2;
y2 = y1 - q * y2;
y1 = t;
}
if (y1 < 0)
y1 += M1;

int x = (b1 * M2 * y2 + b2 * M1 * y1) % (M1 * M2);
printf("同余式组的解为：x ≡ %d (mod %d)\n", x, M1 * M2);

return 0;
}

用c语言编程实现计算同余式组x≡b1(mod m1) x≡b2(mod m2) 的解

#include <stdio.h>

int main()
{
int b1, m1, b2, m2; // 输入的同余式组参数
int M1, M2, y1, y2, x; // 中间变量
printf("输入同余式组：x≡b1(mod m1) x≡b2(mod m2)\n");
printf("请输入b1和m1：");
scanf("%d%d", &b1, &m1);
printf("请输入b2和m2：");
scanf("%d%d", &b2, &m2);
// 计算M1和M2
M1 = m1 * m2;
M2 = m2 * m1;
// 计算y1和y2
for (int i = 1; i < m1; i++)
{
if ((M1 / m1) * i % m1 == 1)
{
y1 = (M1 / m1) * i;
break;
}
}
for (int i = 1; i < m2; i++)
{
if ((M2 / m2) * i % m2 == 1)
{
y2 = (M2 / m2) * i;
break;
}
}
// 计算x
x = (b1 * M2 * y2 + b2 * M1 * y1) % (M1 * M2);
printf("同余式组的解为：x=%d\n", x);
return 0;
}