求解同余方程组21x≡35(mod37),19x≡15(mod19),13x≡25(mod63)
时间: 2023-11-24 17:06:47 浏览: 33
根据中国剩余定理,我们可以先解出一个模数的同余方程组,再通过合并来得到原同余方程组的解。
首先解 21x ≡ 35 (mod 37),我们可以使用扩展欧几里得算法求出 21 在模 37 意义下的逆元为 11,即 21*11 ≡ 1 (mod 37)。因此,两边同乘以 11,得到 x ≡ 11*35 ≡ 26 (mod 37)。
接着解 19x ≡ 15 (mod 19),这个同余方程恒成立,因为 19 在模 19 意义下等于 0。所以,这个方程的任何整数都是解,我们可以将其表示为 x ≡ k (mod 19),其中 k 为任意整数。
最后解 13x ≡ 25 (mod 63),我们可以使用扩展欧几里得算法求出 13 在模 63 意义下的逆元为 17,即 13*17 ≡ 1 (mod 63)。因此,两边同乘以 17,得到 x ≡ 17*25 ≡ 58 (mod 63)。
现在我们需要将这三个同余方程组合并成一个。首先观察其中两个模数互质的方程:
x ≡ 26 (mod 37)
x ≡ k (mod 19)
这个同余方程组的解可以表示为 x ≡ a (mod 37*19),其中 a 是通过中国剩余定理求解得到的一个解。由于 37 和 19 是质数且互质,因此 37*19 = 703 是它们的最小公倍数,满足 x ≡ a (mod 703) 的解就是同余方程组的一个解。
使用相同的方法,我们将末尾的同余方程式合并起来:
x ≡ 58 (mod 63)
再将上一个结果与这个式子求最小公倍数,得到
x ≡ b (mod 703*63)
其中 b 是通过中国剩余定理求解得到的一个解。最终同余方程组的解可以表示为 x ≡ c (mod 21*19*63),其中 c 是 b 在模 21*19*63 意义下的余数。
综上所述,同余方程组21x≡35(mod37),19x≡15(mod19),13x≡25(mod63)的解为 x ≡ c (mod 21*19*63),其中 c 是通过中国剩余定理求解得到的一个解。