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

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小定理构造解,但是手算比较困难.

    另一类是中国剩余定理型的线性同余方程组.

    这个也有系统的方法,你应该也了解吧.