《初等数论》习题解答（第三版）广东石油化工学院
所以
?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．欧拉定理?费马定理及其对循环小数的应用
１、如果今天是星期一，问从今天起再过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即这一天是星期五． ２、求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?
（１）
又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?．由（１）即得?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?．
３、(i)证明下列事实但不许用定理１推论：若p是质数，h1,h2,ha是整数，(h1?h2?h?hpa)p1?hp2?hpa?modp?。
(ii)由(i)证明定理１推论，然后再由定理１推论证明定理１。
证明 (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?
即定理１推论成立。
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 （ｔ＝０、１、２） 即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