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

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

所以

?a???a1??a2??????????.??m??m???m??a?(m)???? ?m??m?ai??aj??ai?左边每一项??都存在另一项?????(i?j),

mm?????m?使得?1?ai??aj???1,右边共有?(m)对, ???2?m??m?此即

?a??1????(m)。 ?2??m??a??1???。 ?2??m?特别地,当m=2时,?(2)?1,3.(i)证明?(1)??(p)?(ii) 证明

??(p?)?p?,p质数。

展布在a的一切正整数上的和式。

da??(d)?a,其中?da证明:(i)因为?(pk)?pk?pk?1,(k?1,2所以?(1)??(p)?,?)

??(p?)

?(p??p??1)

=1?(p?1)?(p2?p)? =p? (ii)设a?p1?1p2?2则

pk?k是a的标准分解式,

?d?(1?p?1dada?p1?1)(1?p2???(p1?1))?p2?2)(1?pk??pk?k),

???(d)?(1??(p1)? =p1?1p2?2 =a 4.若m1,m2,余系,则

M1?1?M?2?2(1??(pk)???(pk?k))

pk?k

,mk是k个两两互质的正整数,?1,?2,,?k 分别通过模m1,m2,,mk的简化剩

?Mk?k

26 / 77

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

通过模m1m2mk?m的简化剩余系,其中m?miMi,i?1,2,,k。

证明:(数学归纳法)

(1) 由定理4知k=2时,结论成立; (2) 设k-1时结论成立,即m??m1模m1,mk?1?miMi?(i?1,,k?1),?1,?2,,?k?1分别过

,mk?1时,

??M1??1?M2??2?过m?模的简化剩余系。

?Mk?1??k?1

显见(m?,mk)?1,则又由定理4知,mk??Mk?k通过模m?mk的简化剩余系,注意到:

mk??(mkM1?)?1?(mkM2?)?2??M1?1?M2?2?

所以,M1?1?M2?2??(mkMk?1?)?k?1

?Mk?1?k?1

?Mk?k通过模m的简化剩余系。

?4.欧拉定理?费马定理及其对循环小数的应用

1、如果今天是星期一,问从今天起再过1010天是星期几?

解:若10101010?1被7除的非负最小剩余是r,则这一天就是星期r(当r?0时是星期日).

?107??1,由费马定理得106?1?mod7?,

又10??2?mod7??1010???2??K?Z?

10?45?4?mod6?

?1010?6K?410?1010?1?106K?4?1?104?1?34?1?5即这一天是星期五. 2、求1237156?34?mod7?

??28被111除的余数。

解:111?37?3.???111????37????3??36?2?72,

??mod37??36据欧拉定理,易知?12371?1?mod111??2?183612371??12371??1?mod3???1237136?1 27 / 77

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

?1237156?1237120?mod111?

(1)

又12371?1112?50?12371?50?mod111?

123712?502??53?mod111??123714?532?34?mod111?

?123718?46?mod111??1237116?7?mod111?

则 1237120?34?7?16?mod111?.由(1)即得?1237156?16?mod111?

?1237156?34?50?mod111???1237156?34?28?5028?mod111?.

由以上计算,知 5020?16?mod111?508?46?mod111?.

??1237156?34?28?5028?16?46?70?mod111?.

3、(i)证明下列事实但不许用定理1推论:若p是质数,h1,h2,ha是整数,(h1?h2?h?hpa)p1?hp2?hpa?modp?。

(ii)由(i)证明定理1推论,然后再由定理1推论证明定理1。

证明 (i)对a应用数学归纳法:

?1?当a?2时,按二项式展开即得

(h1?h2)p?hp1?hp2?modp?

?2?设a?k时,结论成立,即

(h1?h2?hk)p?hpp1?hp2?hk?modp?

当a?k?1时,

(h1?h2?hk?hpk?1)?(h1?h2?hk)p?hpk?1?hp?hp12?hp?hp

kk?1?modp?结论成立。

(ii)在(i)的结论中,令h1?h2??ha?1,即得:

ap?a?modp?

即定理1推论成立。

28 / 77

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

进一步,设m?p1?1ps,则 ??m???pi?1?pi?i?1

?si?1s固对任一整数p,若?a,p??1,则由上述已证性质得:

ap?1?1?modp?存在k?z,使ap?1?1?kp

p故(ap?1)p=?1?kp??1?C1pkp???kp??1?p2l(l?z)

p??ap?1??1?modp2?

p依此类推可得(a若

p?1)p??1?1?modp则

??,即a?i?p???1?modp??.

,i?a,m??1,

??a,?p??1?i??21 ,sa,?pi?i???1modp??.i?

i?a??m??1?modpi?i?,?i?1,2,4、证明:有理数

s??a??m??1?modm?,定理成立。

a,0?a?b,?a,b??1表成纯循环小数的充分与必要条件是有一正数t使得同b余式10t?1?modb?成立,并且使上式成立的最小正整数t就是循环节的长度。 证明:?i?必要性,若结论成立,则由定理2知(b,10)=1, 令t=??b?,则据欧拉定理得10t?1?modb?;

a2充分性,若有正数t,满足10t?1?modb?

令t为使上式成立的最小正整数,且10t=q1b?1

?10ta??aq1?b?a?qb?a,?q?a1q?

且0?qab10ta?1??10t?1???10t?1。 b?b?以下参照课本51页的证明可得:

.a=0.a1baat.即可表成循环小数,但循环节的长度就是t。

b.

29 / 77

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

第四章 同余式

?1 基本概念及一次同余式

例 解同余式 12x?15?0?mod45? 解:

(12,45)=315

?同余多项式有3个解 而原同余式为4x?5?0?mod15? 4x??5?mod?1 5 4?4x??20?mod15? 15x?x??2?0mod? 15?x0?10(mod15)与x0??5(mod45)也一样

所以原同余式的3个解是x?10?15t (t=0、1、2) 即x1?10(mod15),x2?25(mod15),x3?40(mod15) 1、 求下列各同余式的解 ?i?256x??30?179?mod337? 2?5?? ?ii?1215x?560?mod2755?

?iii?1296x?1125?mod1935?

?i?337是素数, ??256,337??1,原同余式有唯一解。

先解同余式256x??30?1mod337? 2???5?由辗转相除法,得256?104?337??79??1

?上述同余式的解是x?104?mod337? ?原同余式的解是x?104?179?81?mod337?

?ii?(1215,2755)=5,故先解

30 / 77