作业帮同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 20:15:19
同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
同余式x^2=29(mod 35)的所有解怎么求?
如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
这个方程等价于同余方程组:x² ≡ 29 (mod 5),x² ≡ 29 (mod 7).
因为若x满足x² ≡ 29 (mod 35),易见x也满足上述方程组.
反过来,若x满足上述方程组,则x²-29被5和7整除,于是被35整除,即有x² ≡ 29 (mod 35).
分别求解方程组中的两个方程.
x² ≡ 29 ≡ 4 (mod 5),即5 | x²-4 = (x-2)(x+2),得x ≡ ±2 (mod 5).
x² ≡ 29 ≡ 1 (mod 7),即7 | x²-1 = (x-1)(x+1),得x ≡ ±1 (mod 7).
于是只需求解以下4个线性同余方程组(其实只需解前两个,后两个取负号):
x ≡ 2 (mod 5),x ≡ 1 (mod 7);
x ≡ 2 (mod 5),x ≡ -1 (mod 7);
x ≡ -2 (mod 5),x ≡ 1 (mod 7);
x ≡ -2 (mod 5),x ≡ -1 (mod 7).
解得x ≡ ±8,±13 (mod 35).
总结起来,需要解两类方程.
一类是mod质数(方幂)的二次同余方程.
对较小的质数可以枚举求解,上面也是这么做的(两个方程的解都可以直接看出来).
对较大的质数可利用借助Fermat小定理构造解,但是手算比较困难.
另一类是中国剩余定理型的线性同余方程组.
这个也有系统的方法,你应该也了解吧.