初等数论高阶同余式求解 6x^70+27x^24+17x^4+20x==0(mod45)

1个回答

  • 首先因为mod 5和mod 9的剩余类不多, 所以其实逐个验算其实也行的.

    简化计算可以从以下方面入手.

    1. 用Fermat-Euler定理降次.

    若(a,m) = 1, 则a^φ(m) ≡ 1 (mod m).

    因此当x不被5整除, 有x^4 ≡ 1 (mod 5), 进而x^24 = (x^4)^6 ≡ 1 (mod 5),

    x^70 = (x^4)^17·x² ≡ x² (mod 5).

    当x不被3整除, 有x^6 ≡ 1 (mod 9), 进而x^70 = (x^6)^11·x^4 ≡ x^4 (mod 9).

    需要注意的是, 为了使用此简化, 需要单独讨论x与模数不互质的情况.

    对本题, 易见x ≡ 0 (mod 5)是6x^70+27x^24+17x^4+20x ≡ 0 (mod 5)的解.

    当x ≡ 0 (mod 3)时, 易见0 ≡ 6x^70+27x^24+17x^4+20x ≡ 2x (mod 9), 解得x ≡ 0 (mod 9).

    以下只讨论x与模数互质的情况.

    方程变为x²+4 ≡ 0 (mod 5)与5x^4+2x ≡ 0 (mod 9).

    由(x,9) = 1, 2·5 ≡ 1 (mod 9), 后者可进一步化为x³+4 ≡ 0 (mod 9).

    2. 分解因式.

    在mod 5意义下, x²+4 ≡ x²-1 = (x-1)(x+1).

    x²+4 ≡ 0 (mod 5)即5 | (x-1)(x+1), 由5是质数, 有5 | x-1或5 | x+1.

    即得x ≡ 1, 4 (mod 5).

    其实分解因式也没有什么特别有效的办法, 试根也许更快.

    不过在找到一个根以后, 可以用因式分解降次.

    3. 模数约化.

    先解x³+4 ≡ 0 (mod 3).

    在mod 3意义下, x³+4 ≡ x+1, 于是由x³+4 ≡ 0 (mod 3)解得x ≡ 2 (mod 3).

    设x = 3y-1, 则在mod 9意义下, x³+4 = (3y-1)³+4 = 27y³-27y²+9y-1+4 ≡ 3.

    因此x³+4 ≡ 0 (mod 9)无解.

    综上, 解得x ≡ 0, 1, 4 (mod 5), x ≡ 0 (mod 9).

    求解该线性同余方程组得x ≡ 0, 9, 36 (mod 45).