内容发布更新时间 : 2024/11/8 14:47:12星期一 下面是文章的全部内容请认真阅读。
《初等数论》习题解答（第三版）广东石油化工学院
?ii?设(1)有解c，即c?b1(modm1),c?b2(modm2)
故此得b1?b2(mod(m1,m2))，必要性成立； 反之，设d|b1?b2即b1?b2(modd)
则由§1定理，知方程m1y?b2?b1(modm2)必有解， 设其解为y?y0(modm2)，即m1y0?b2?b1(modm2) 令x1,2?b1?m1y0则易见：
x1,2?b1(modm1)且x1,2?b2(modm2)
即(1)有解x1,2，充分性得证。 进一步，若(1)有解x,y，则
x?y(modm1),x?y(modm2)
即x?y是m1,m2的公倍数，当然也是?m1,m2?的倍数，
?x?y(mod?m1,m2?)
故若x1,2是(1)的一个解，则(1)的任一解x必满足
x?x1,2(mod?m1,m2?)。
(iii)若同余式组x?bi(modmi),i?1,2,则?,k有解，
??x?bi(modmi) 也有解。从而由(ii)知必有
??x?bj(modmj),k，必要性成立。
(mi,mj)|(bi,bj),i?1,2,下证充分性。首先，推(i)，用归纳法易证：
?(m1,mk),(m2,mk),,(mk?1,mk)??(?m1,m2,,mk?1?,mk)
又由(ii)知k?2时，充分性也成立；
36 / 77
《初等数论》习题解答（第三版）广东石油化工学院
?x?b1(modm1)?现设同余式组? 有解x?b(mod?m1,?x?b(modm)k?1k?1?即b?bi(modmi),1?i?k?1。
设bi?b?limi,1?i?k?1；又由条件知(mi,mk)|(bi?bk)，
,mk?1?)，
而bi?bk?(b?bk)?limi，从而(mi,mk)|bi?bk,1?i?k?1， 所以x2?41(mod16)， 即(?m1,m2,,mk?1?,mk)?b?bk，
??x?b(mod?m1,,mk?1?)又由(ii)，则同余式组?，
??x?bk(modmk)必有解x?c(mod?m1,,mk?1,mk?) （※）
显然c?bi(modmi),1?i?k，即（※）就是同余式组(2)的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。
§3 高次同余式的解数及解法
1、 解同余式6x3?27x2?17x?20?0(mod30)。
?x2?x?0(mod2)??????????(1)?解：原同余式等价于?2x?2?0(mod3)??????????(2)
?x3?2x2?2x?0(mod5)??????(3)?(1)有解x?0,1(mod2) (2)有解x?2(mod3) (3)有解x?0,1,2(mod5)
?x?b1(mod2)? 联立?x?b2(mod3)?x?b3(mod5)?b1?0,1b2?2b3?0,1,2
据孙子定理，可得x?15b1?10b2?6b3(mod30)
37 / 77
《初等数论》习题解答（第三版）广东石油化工学院
故原同余式共有6个解是：
x1?20,x2?5,x3?26,x4?11,x5?2,x6?17,(mod30)
2、 解同余式31x4?57x3?96x?191?0(mod225)
解：
225?32?52
?4x4?3x3?6x?2?0(mod32)? 故原同余式等价于?4 32??6x?7x?4x?9?0(mod5)1） 先解4x4?3x3?6x?2?0(mod3)
即x4?1?0(mod3) 得x??1(mod3)
f?(x)?16x3?9x2?6?f?(1)?31,3?31
f?(?1)??1,3?(?1)f(1)??5(mod3)?t1?1(mod3).3?x1?1?3t1?4(mod32);由f?(1)t1??又由f?(?1)t2??5(mod3)?t2?2(mod3)?x2??1?3t2?5(mod32);即第一式有两个解x1?4,x2?5②再解g(x)?6x4?7x3?4x?9?0即 x4?2x3?x?1?0设 x?1,
(mod32).(mod5)
(mod5)
2(mod 5g?(1)?41.g?(2)?272,
g?(x)?24x3?21x2?4.而5?415?272
(mod5)(mod5)(mod52).
由41t1?0(mod5)?t1?0272t2??27(mod5)?t2?4?3?第二式有两个解x3?1,?x?b1联立??x?b2(mod9)(mod25)b1?4,5b2?1,?3 38 / 77
《初等数论》习题解答（第三版）广东石油化工学院
由孙子定理设x?100b1?126b2即原四条式有4个解是x?76, §4．质数模的同余式
补充例子： 1．解同余方程：
(mod225)
22,176,122(mod225).
(ⅰ) 3x11 ? 2x8 ? 5x4 ? 1 ? 0 (mod 7)； (ⅱ) 4x20 ? 3x12 ? 2x7 ? 3x ? 2 ? 0 (mod 5)。
解：(ⅰ) 原同余方程等价于3x5 ? 5x4 ? 2x2 ? 1 ? 0 (mod 7)，用x = 0，?1，?2，?3代入知后者无解； (ⅱ) 原同余方程等价于2x4 ? 2x3 ? 3x ? 2 ? 0 (mod 5)，将x = 0，?1，?2 代入，知后者有解x ? ?1 (mod 5)。 2．判定
(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)是否有三个解； (ⅱ) x6 ? 2x5 ? 4x2 ? 3 ? 0 (mod 5)是否有六个解？
解：(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)等价于x3 ? 3x2 ? 4x ? 3 ? 0 (mod 5)，又x5 ? x = (x3 ? 3x2 ? 4x ? 3)(x2 ? 3x ? 5) + (6x2 ? 12x ? 15)，其中r(x) = 6x2 ? 12x ? 15的系数不都是5的倍数，故原方程没有三个解； (ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。
定理5 若p是素数，n?p ? 1，p?|a则
x n ? a (mod p) (14)
有解的充要条件是
p?1na若有解，则解数为n。
?1 (mod p)。 (15)
证明 必要性 若方程(14)有解x0，则p?|x0，由Fermat定理，得到
39 / 77
《初等数论》习题解答（第三版）广东石油化工学院
a充分性 若式(15)成立，则
p?1n?(x)n0p?1n= x0p ? 1 ?1 (mod p)。
p?1np?1np?1nxp?1?x?x((x)n?a?a?1)?(xn?a)P(x)?x(ap?1n
?1)，其中P(x)是关于x的整系数多项式。由定理4可知同余方程(14)有n个解。证毕。
1、 设n︱p?1， n?1， (a,p)?1．证明同余式 xn?a有解的充分必要条件是a(modp )p?1n?1(modp)，并且在有解的情况下就有n个解。
证明：?)若同余式有解，令其解为x?x0(modp), 设p?1?kn.则x0p?1?x0kn?1但x0p?1?a(a,p)?1,?(x0,p)?1 (modp)
(modp)
?ap?1n?x0p?1?1(modp);
?)ap?1n?1(modp)
(modp) 可得xp?1则由x?an?ap?1n?1(modp)。
它有p?1个解。
又n︱p?1
p?1p?1?2?1??(p?1)?n(p?1)?2nnnn?ax?ax?a 令g(x)??x?
??则xp?1?(xn?a)g(x)?0(modp)
g(x)?0(modp)
40 / 77