《初等数论(闵嗣鹤、严士健)》第三版习题解答 下载本文

《初等数论》习题解答(第三版)广东石油化工学院

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