Question

同余式x^2=29(mod 35)的所有解怎么求？

如题，这个题的解跟29mod5 和 29mod7的逆有什么关系？

Answer 1

这个方程等价于同余方程组: 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小定理构造解, 但是手算比较困难.
另一类是中国剩余定理型的线性同余方程组.
这个也有系统的方法, 你应该也了解吧.