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

首先因为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).