《初等数论》习题解答（第三版）广东石油化工学院
243x??30?112?mod551? 2?5??同?i?的方法的得其解是x?200?mod551?
?原同余式的解是x?200,751,1302,1853,2404?mod2755?
?iii?(1296，1935)=9，故原同余式有9个解。
由144x??30?125?mod215?得x?80?mod215? 2?5???原同余式的解是x?80?215t?mod1935?,t?0,18.
2．求联立同余式??x?4y?29?0(mod143)的解。
2x?9y?84?0(mod143)?解：据同余式的有关性质，
?x?4y?29?0(mod143)?x?4y?29(mod143) ????2x?9y?84?0(mod143)?17y??1(mod143)?x?4y?29(mod143)?x?4(mod143)为所求的解。 ????y?42(mod143)y?42(mod143)??3．(i)设m是正整数，(a,m)?1．证明
?(m?)1(modm ) x?ba是同余式 ax?b(modm)的解 (ii)设p是质数，0?a?p，证明
x?b(?1)a?1(p?1)(p?a?1)(modp)
a!是同余式ax?b(modp)的解． 证明: (i)
(a,m)?1 ， ?ax?b(modm) 有唯一解．
而据欧拉定理，得 a?(m)?1(modm)，
31 / 77
《初等数论》习题解答（第三版）广东石油化工学院
ax?b(momd)?a?(m?)1?ax?ba?m(?)1(momd)
即 x?ba?(m)?1(modm)是ax?b(modm)的解． (ii) 又
0?a?p?(a,p)?1 即ax?b(modp)有唯一解
a个连续整数之积必被a!所整除，
(p?1)(p?a?1)故可令 ab(?1)a?1?k
a!则b(?1)a?1(p?1)(p?a?1)?k(a?1)!
(p?a?1)?b(?1)2(a?1)(a?1)!(modp)
b(?1)a?1(p?1)即b(?1)2(a?1)(a?1)!?k(a?1)!(modp)
?k?b(modp)
即 x?b(?1)a?1(p?1)(p?a?1)(modp)
a!是ax?b(modp)的解．
设p是素数，0 < a < p，证明：
x?b(?1)a?1(p?1)(p?2)???(p?a?1)(mod p)。
a!是同余方程ax ? b (mod p)的解。
(p?1)(p?2)???(p?a?1)是整数，又由(a, p) = 1知方程ax ?
a!(p?1)(p?2)???(p?a?1)b (mod p)解唯一，故只须将x?b(?1)a?1(mod p)代入ax ? b
a!解：首先易知b(?1)a?1(mod p)验证它是同余方程的解即可。
4．设m是正整数，?是实数，1???m,(a,m)?1，证明同余式
ax?y(modm),0?x??,0?y?有解．
m?
32 / 77
《初等数论》习题解答（第三版）广东石油化工学院
证明: 因(a,m)?1. 故同余式 ax?1(modm) 必有解x0， (i) (ii)
若 0?x0??，则结论成立;
若??x0，令m?q1x0?x1，0?x1?x0， 则ax1??(ax0)q1??q1(modm)
又若 x1??,则由 q1?m?x1m?，结论成立． x0?若 ??x1 令 x0?q2x1?x2 则 ax2?1?q1q2(modm).
0?x2?x1
又若 x2??,则由m?q1x0?x1?q1(q2x1?x2)?x1 即m?(1?q1q2)x1?q1x2, 故 1?q1q2?结论成立。
若??x2,又令x1?q3x2?x3, 0?x3?x2. 则 ax3??(q1?q2?q1q2q3)(modm) 重复上述讨论：即若
m?q1x2m? x1?x3??,则结论成立，
若??x3.又令 x2?q4x3?x4,0?x4?x3 ``````
?x?2(mod3)? 例解同余方程组?x?3(mod5)
?x?2(mod7)?解：
模3,5,7两两互质，故原方程组对模m?3?5?7有唯一解
33 / 77
《初等数论》习题解答（第三版）广东石油化工学院
35M1??1(mod3)得M1??2(mod3)??1(mod5)21M2??1(mod5)M1M1??1(mod3)即M2??1(mod7)15M3??1(mod7)M3根据孙子定理方程组的解是
x?2?35?2?1?21?3?1?115?2?233?23(mod105)
注意到 x0?x1?x2?,
故有限步后，必有 axn?y(modm) 其中0?xn??,y?m?,即结论成立。
?2.孙子定理
试解下列各题：
（i） 十一数余三，七二数余二，十三数余一，问本数。 （ii） 二数余一，五数余二，七数余三，九数余四，问本数。 （杨辉：续古摘奇算法（1275））。
?x?3(mod11)?解：（i）依题意得?x?2(mod72)
?x?1(mod13)?则据孙子定理，上述方程组有唯一解(mod11?72?13)
72?73M1??1(mod11)得M1??1;??1(mod72)得M2???1; 由11?13M2??1(mod13)得M3???1;11?72M3故原方程组的解是x?3?936?2?(?1)?143?1?(?1)?792?1730(mod10296).
?x?1(mod2)?x?2(mod5)?(ii)依题意得?
x?3(mod7)???x?4(mod9)?x?1?315?2?126?3?6?90?4?4?70?3307?157(mod630).
2、（i）设 m1,m2,m3是三个正整数，证明：
34 / 77
《初等数论》习题解答（第三版）广东石油化工学院
???(m1,m3),(m2,m3)?????m1,m2?,m3?．
（ii）设 d?(m1,m2).证明：同余式组
?, x?b1(modm1)x2b(momd)1） （2有解的充分与必要条件是db1?b2.
在有解的情况下，适合（1）的一切整数可由下式求出：
x?x1,2?mod?m1,m2??
其中x1,2是适合?1?的一个整数。
?iii?应用?i?,?ii?证明同余式组x?bi?modmi?,i?1,2,有解的充分与必要条件是(mi,mj)|(bi,bj),i,j?1,2,整数可由下式求出：
,k ?2?
,k，并且有解的情况下，适合(2)的一切
x?x1,2,其中x1,2,,k(mod?m1,m2,mk?)
,k是适合(2)的一个整数。
证明：?i??(m1,m3),(m2,m3)??(m1,m3)(m2,m3)(m,m)(m2,m3)?13
((m1,m3),(m2,m3))(m1,m2,m3)3 (?m1,m2?,m3)?((mm,(m,1m)2m)3(mm1,m2m,1mmm1m23)2,m3)?12?
(m1,m2)(m1,m2)(m1,m2)(m1,m2,m3)(m1m2,m1m3,m2m3)?((m1,m2,m3)m1m2,(m1,m2,m3)m1m3,(m1,m2,m3)m2m3)
22222?(m12m2,m1m,mm,mm,mm,mm3m1m2)m(3,m1)m(221313232,m1)m( 3m2)m3?(m12,m1m3,m1m2,m2m),m3)3(m2222?(m12m2,m1m,3m22m,32m1m,33,mmmm2,m2m112)3m1m2,m1m3,m2?m3) ?(m1,m2,m3)(即
(m1,m2)(m1,m3)(m ,m)(m1,m3)(m2,m3)(m1m2,m1m3,m2m3)?
(m1,m2,m3)(m1,m2) ??(m1,m3),m(2m,3??)?m(1?m,2m, 3). 35 / 77