《初等数论》第三版习题解答

第一章 整数的可除性 1 整除的概念带余除法 1 证 明 定 理 3 定 理 3 若 都 是 得 倍 数 ， 是 任 意 n 个 整 数 ， 则12na， ， ， m12nq， ， ， 是 得 倍 数 12nqaq 证明： 都是 的倍数。12, 存在 个整数 使 12,np 12,napapm 又 是任意 个整数12,nq naqa12pmpm()nq 即 是 的整数12aqa 2证明 3|(1) 证明 (1)2)nnn ()( 又 ， 是连续的三个整数(1)2() 故 3|,3|1nn|()() 从而可知 |2 3若 是形如 （x，y 是任意整数，a， b 是两不全为零的整数）的数中最0axbyab 小整数，则 ()|() 证： 不全为,ab 在整数集合 中存在正整数，因而有形如 的最小整数|,SaxbyZaxby0axby ，由带余除法有,Z00(),axbyqrxy 则 ，由 是 中的最小整数知00()()rxqS0xbySr 0|aby （ 为任意整数） |x,xy00|,|axyxby 又有 ，0(,).()|ab(,)|b 故0(,)|ab0 4若 a，b 是任意二整数，且 ，证明：存在两个整数 s，t 使得|,2abst 成立，并且当 b 是奇数时，s，t 是唯一存在的当 b 是偶数时结果如何？ 证：作序列 则 必在此序列的某两项之间33,0,22b a 即存在一个整数 ，使 成立q1qa 当 为偶数时，若 则令 ，则有()i 0.b,22qstbsa02qqasta 若 则令 ，则同样有b,2tbs2bt 当 为奇数时，若 则令 ，则有()iq011,qqtas10222b bqtasba 若 ，则令 ，则同样有 ， 综上所述，存在性01,qts2bt 得证 初等数论习题解答（第三版） 3 / 77 下证唯一性 当 为奇数时，设 则b1abstt1()tbs 而 矛盾 故111,2tttt1,t 当 为偶数时， 不唯一，举例如下：此时 为整数b,st 2b1312(),2bt 2 最大公因数与辗转相除法 1证明推论 4.1 推论 4.1 a，b 的公因数与（a，b）的因数相同 证：设 是 a，b 的任一公因数， |a， |bd d 由带余除法 122111,0nnnqrrrb (,)ab | ， | ，, | ,d1qrd12rqd21()nnrqrab 即 是 的因数。(,)ab 反过来 | 且 | ，若 则 ，所以 的因数都是 的公(,)|(,)dab|,|db(,)a,ab 因数，从而 的公因数与 的因数相同。, 2证明：见本书 P2，P3 第 3 题证明。 3应用1 习题 4 证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求 法及辗转相除法实际算出（76501，9719） 解：有1 习题 4 知： 使 。 ，,0,abZstZ,|2bast ，使 如此类推知：1st1|2 2,;nnst111nst 且 21| 2nnttbt 而 b 是一个有限数， 使,N10nt ，存在其求法为：12(,),(,),(,)(,natt t 1sabs(7650,9)17)84,68(213,1) 4证明本节（1）式中的 log2bn 证：由 P31 习题 4 知在（1）式中有 ，而21102nn nrrb 1nr ， ，即,2blogllog2b 3 整除的进一步性质及最小公倍数 1证明两整数 a，b 互质的充分与必要条件是：存在两个整数 s，t 满足条件 1axbt 证明 必要性。若 ，则由推论 1.1 知存在两个整数 s，t 满足： ，(,)1 (,) 初等数论习题解答（第三版） 5 / 77 1asbt 充分性。若存在整数 s，t 使 as+bt=1，则 a，b 不全为 0。 又因为 ，所以 即 。(,)|,|ab(,|)st(,)|1 又 ，0b1 2证明定理 3 定理 3 1212,|,|,|nnaa 证：设 ，则,m 1|(,)i 又设1|(,)ia 22|,|,|nam 则 。反之若 ，则 ，2|m2|i|i1| 从而 ，即 =11,na 122|,|,|na 3设 （1）10nnxx 是一个整数系数多项式且 ， 都不是零，则（1）的根只能是以 的因数作分子以an 0a 为分母的既约分数，并由此推出 不是有理数na2 证：设（1）的任一有理根为 ， 。则pq(,)1q110()()nnpaaq （2）110nnnnpq 由 ，10(2) nnapaq 所以 q 整除上式的右端，所以 ，又 ，|np(,)1 所以 ；(,)1,|nnpa 又由（2）有 110nnpqapq 因为 p 整除上式的右端，所以 ， ，所以0|nPaq(,)1pq(,)1, |nnpa 故（1）的有理根为 ，且 。pq0|,|n 假设 为有理数， ，次方程为整系数方程，则由上述结论，可知其22,x 有有理根只能是 ，这与 为其有理根矛盾。故 为无理数。1,2 另证，设 为有理数 = ，则2,pq()1,22222,()(,)pq 但由 知 ，矛盾，故 不是有理数。(,)12,1pq 4 质数算术基本定理 1试造不超过 100 的质数表 解：用 Eratosthenes 筛选法 （1）算出 a01 （2）10 内的质数为：2，3，5，7 （3）划掉 2，3，5，7 的倍数，剩下的是 100 内的素数 将不超过 100 的正整数排列如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 初等数论习题解答（第三版） 7 / 77 2求 82798848 及 81057226635000 的标准式 解：因为 8|848，所以 ，38|,279841098562AB 又 8|856，所以 8|B， ，31BC 又 4|32，所以 4|C， 24CD 又 9|（3+2+3+4+3+3） ，所以 9|D， ，29357E 又 9|（3+5+9+3+7） ，所以 9|E， E 又 3391 所以 ；8532A 同理有 。34320760257137 3证明推论 3.3 并推广到 n 个正整数的情形 推论 3.3 设 a，b 是任意两个正整数，且 ， ， ，12np 0i1,2ik ， ， ，b 则 ， ，12(,)kap 12,kabp 其中 ， ，min(,)iiin(,)ii,i 证： ，,ii0,iiii |,|iiiipp(1,2)k ， .1ii ki1iik ，又显然2|(,)kpab 12(,)|kabp ，同理可得 ，12k 12,kab max,ii 推广 设 , ,112kap 221kap 12nnkap (其中 为质数 为任意 n 个正整数 )， 则j,ij ,0iji12121(,),mi,1,2iiiknijijnpa k 12,ax,iiik ijiji 4应用推论 3.3 证明3 的定理 4（ii） 证：设 ，1212k kapbp ， 其中 p1, p2, , p k 是互不相同的素数， i， i（1 i k）都是非负整数，有12()mn,axkiiabpi ， ， ， ， 。 由此知( a, b)a, b = =ab；从而有 min,a,111i ii i kk kii ipp,(,)ab 若 是质数（n1） ，则 n 是 2 的方幂n2 证：（反证法）设 为奇数） ，2(kl 则 222(1)2()1)11kkkkknll ll ，2(kkln 为合数矛盾，故一定为的方幂21n 5 函数x,x及其在数论中的一个应用 1 求 30！ 的 标 准 分 解 式 解 ： 30 内 的 素 数 为 2， 3， 5， 7， 11， 13， 17， 19， 23， 292234500154323400 10314 初等数论习题解答（第三版） 9 / 77 52330061075 ，724 123021 ，13002 3 0 ，721 19239 314520!7 2设 n 是任一正整数，是实数，证明： (i) (ii) 11nn 证：(i)设 .则由性质 II 知 ,mm 所以 ,n 所以 ，所以 ，又在与+之间只有唯一整数，n1 所以 m (ii) 证法一 设 ,1,0,21kknn 则 ,k 当 时, ;1in1,ikiinn 当 时, ;ik2,1iii 11100()()nnkni iikik 10nii 证法二 令 , 10()niif10()1()niif nf10()()niif f 是以 为周期的函数。()fn 又当 ，,1()0,()0f Rf时 即 。0 ni 评注：证一充分体现了 常规方法的特点，而 证二则表现了较高的技巧。 3设 ， 是任意二实数，证明： (i) 或1 (ii) 2 证明：（i）由高斯函数x的定义有 。则 ,01;rsrs , 当 ,时 初等数论习题解答（第三版） 11 / 77 当 0,1rs时 故 或 （ii）设 ，,01xyx 则有 02y 下面分两个区间讨论： 若 ，则 ，所以 ，所以1xy0xy2222()xy2 若 ，则 ，所以 。1xy1xy1 所以 1222()12()2xyxyyx （ii） （证法 2）由于 ， 对称，不妨设()2()2() 4. (i) 设函数 在闭区间 上是连续的，并且非负，证明:和式QxR 表示平面区域 ， 内的整点（整数坐标的点）的个数.QxR0()yfx (ii) 设 p，q 是两个互质的单正整数，证明： (iii) 设 ，T 是区域 内的整点数，证明： (iv) 设 ，T 是区域 ， ， 内的整点数，证明： 证明：( 略) 5. 设 任一正整数，且 ，p 是质数， ，证明：在 的标准分解式中，质因数 p 的指数是 其中 . 证明：在 的标准分解式中，质因数 p 的指数有限，即 ， 所以 初等数论习题解答（第三版） 13 / 77 而 第二章 不定方程 21 习题 1、解下列不定方程 63030)yxb)152axy 解： 原方程等价于： 显然它有一个整数解 ， )a3 1,2 故一般解为 0(,12,)2xty 原方程等价于： 显然它有一个整数解 )b173500735,6xy 故一般解为 0(,12,)6xty 2、把 100 分成两份，使一份可被 整除，一份可被 整除。7 解：依题意 即求 的正整数解，解得 71x08,4xy 一般解是： 8(0,1)4ty 但除 外无其他正整数解，故有且只有 0t 0564 3、证明：二元一次不定方程 ,()1axbyNba 的非负整数解为 或 Nb1 证明：当 时，原方程没有整数解，而 故命题正确010ab 当 时，原方程有且只有一个非负整数解 而 0N0,0Nab1 因为 所以 ,1ab 原方程有整数解 10 1021,(),(),n nn nxyqxq 其中 ，由于 ，故 中一正一负，可设123,nqb 0aby0,xy 原方程的一般解是： 0,1xty 要求 ，0000, yxbtattba 仅当 是整数时，才能取 ，否则 ya0t0yta 故这个不等式的整数解个数 是 ：T 当是整数时 00011xyxyTbab 因而 0NNTa 当 不是整数时 0y0001xyxybaba 因而 所以 01Nabxya()m 证 明 2： 二 元 一 次 不 定 方 程 ax by = N 的 一 切 整 数 解 为 ， tZ， 于0xbya 是 由 x 0， y 0 得 ， 但 区 间 的 长 度 是 ， 故 此 区 间 内 的00yt0,xabN 整 数 个 数 为 1。Nab或 ： 初等数论习题解答（第三版） 15 / 77 4、证明：二元一次不定方程 ，当 ,()1,axbyNabNab 时有非负整数解， 则不然。N 证明：先证后一点，当 时，原方程有非负整数解 0,xy 则 12(,).dm00001,1bxayxbkyahk ，这是不可能的。,2kh 次证，当 Nab-a-b 时，因(a，b)=1 ，故原方程有整数解（x ，y ） ，一般解是0 要求 x -bt 0，y 会证明存在满足这个不等式的0(,1)xbtya at0yxtb 整数 可取使 于是对于这个 有：0t0()btrb0 而1xbr0000 11()()()()1aytxbyaxbNababt 这就证明了当 时，原方程有非负整数解Na 1 证 明 定 理 2 推 论 。 推论 单位圆周上座标都是有理数的点（称为有理点） ，可以写成222 2, ,()()ababa或 的形式，其中 a 与 b 是不全为零的整数。 证 明 ： 设 有 理 数 （ m 0） 满 足 方 程 x2 y2 = 1， 即 l2 n2 = lnxy， m2， 于 是 得 l = 2abd， n = (a2 b2)d， m = (a2 b2)d 或 l = (a2 b2)d， m = 2abd， m = (a2 b2)d， 由 此 得 (x, y) = 。 反 之 ， 代 入 方 程 x2 y2 = 1 即 知 这 样 222 2, ,()()abab或 的 点 在 单 位 圆 周 上 。 2求出不定方程 的一切正整数解的公式。223,()1,0,xyzxyz 解：设不定方程 有解则 (1) 3/z-x 或 3/z+x 因为 22()yzxzx 或 3/z+x3/()3/zx22 233/zxzxzxy或 者得 或 以下不妨设 ， 设 ,122(,z)d/x,zd/,y则 与 矛盾!223/9/93d若 3,x1y 这样 而2, /y/,d ， ，12zx或 ,()2tzxtzxx设 即 /()/.2tz1或 若 ,1,3xzxz则223zxyy从 而 由引理可设 2,xa,ab 从而 ， 为证得 为整数， z1,xz 必须有 a ， b 均为奇数，且 23 若 , ,1,162zxzxzx 初等数论习题解答（第三版） 17 / 77 2236yzxzxy从 而 设 ，2222,3,36abyabz即 其中 为一奇一偶，且有,ab1 4 解 不 定 方 程 ： x2 3y2 = z2， x 0， y 0， z 0， (x, y ) = 1。 解 ： 设 (z x, z x) = d， 易 知 d = 1 或 2。 由 (z x)(z x) = 3y2 得 z x = 3da2， z x = db2， y = dab 或 z x = db2， z x = 3da2， y = dab， a 0， b 0， (a, b ) = 1。 ( ) 当 d = 1： ， a 0， b 2|ayb， ， 0， (a, b ) = 1， 3 b， a, b 同 为 奇 数 ； ( ) 当 d = 2： x = |b2 3a2|， y = | 2ab， z = b2 3a2， a 0， b 0， (a, b ) = 1， 3 b， a, b 一 奇 一 偶 。 反 之 ， 易| 验 证 ( )或 ( )是 原 不 定 方 程 的 解 ， 且 x 0， y 0， z 0， (x, y) = 1。 3证明不等式方程 的一切正整数解24,/yxxz 可以写成公式: ，()ab4262z 其中 0,1,a一 单 一 双 证明:由定理 1 知道原方程的解是 22,xcdyzcd ， 且 c， d 为一奇一偶，,cd 其中， ， 且 a， b 为一奇一偶2,0,1abab 所以 ， 是原方程的正整数解4()xy4262z ，(0,1,2/yzx且 是 奇 数 原方程正整数的解有: ， ，,， ， 2,a， 2,0a24224(),(6),()baba4(6)4(),b 6 求 方 程 x2 y2 = z4 的 满 足 (x, y ) = 1， 2x 的 正 整 数 解 。 解 ： 设 x， y， z 是 x2 y2 = z4 的 满 足 (x, y) = 1， 2x 的 正 整 数 解 ， 则 x = 2ab， y = a2 b2， z2 = a2 b2， a b 0， (a, b) = 1， a, b 一 奇 一 偶 ， 再 由 z2 = a2 b2 得 a = 2uv， b = u2 v2， z = u2 v2 或 a = u2 v2， b = 2uv， z = u2 v2， u v 0， (u, v) = 1， u, v 一 奇 一 偶 ， 于 是 得 x = 4uv(u2 v2)， y = |u4 v4 6u2v2|， z = u2 v2， u v 0， (u, v) = 1， u, v 一 奇 一 偶 。 反 之 ， 易 验 证 它 是 原 不 定 方 程 的 整 数 解 ， 且 x 0， y 0， z 0， (x, y) = 1， 2x。 其中正负号可任意选取 第三章 同余 1 同余的概念及其基本性质 1、 证明（i）若 (modm)1kA 1k x y (modm)、i=1 ，2， 、 、 、 ，kii 则 (modm)1 11 11, k kk kk kxy 特别地，若 （modm） ，i=0，1， 则iab,n （modm）10 0nnnxxbb (ii)若 a b(modm)，k ,(mod),akA （iii）若 a b(modm)，d 是 a，b 及 m 的任一正公因数，则 (mod),ab (iv)若 a b(modm)， 则 a b(modd),0. 证明 ：（i）据性质戊，由 (od),12,.iixyik 得 (mod),12,iixyik 进一步，则 1 11 1(od)k kk kBymA 最后据性质丁，可得： 初等数论习题解答（第三版） 19 / 77 （modm）1 11 11, k kk kk kxyA (ii) 据定理 1，a b(modm) ,mab0,()kmkbk 又据定理 1，即得 (od). （iii）据定理 1， a b(modm) 即 a-b=ms(s z),mab ，即,0,bdabmsd,sd 仍据定理 1，立得 (o), (iv) 据定理 1， a b(modm) ,(),amsz 又 ,dmtz 故 (),abs(o. 2、设正整数 100,1nniaa 试证 11 整除的充分且必要条件是 11 整除 1().ini 证明 ： 由上题(i)的特殊情形立得10(mod1),0nnaa 10()()(mod1)nnaa0(1)od),ii 0() iniaa 3找出整数能被 37，101 整除有判別条件来。 解： 1(mod37) 故正整数 1010,10kkiaaa 立得 037.i10(mod1). 故设正整数 ，10,1ssiabb 立得 010(). sii 4、证明 6321 证明： 85mod64 1625od641 371 即 42 5、若 是任一单数，则 ，a2modnna1 证明：（数学归纳法）设 1 （1） 时， ，n 224od8 结论成立。 （2）设 时，结论成立，即：k ，2 22 20mod1 kk ktz 而 1kkkkkaaa 22kktt 43 312kkt 0mod 故 时，结论也成立； 时，结论也成立。1nkn 证明：若 2 a，n 是正整数，则 1 (mod 2n + 2)。 (4)|2na 初等数论习题解答（第三版） 21 / 77 设 a = 2k 1，当 n = 1 时，有 a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)， 即式(4)成立。 设式(4)对于 n = k 成立，则有 1 (mod 2k + 2) = 1 q2k + 2，2k ka 其中 qZ，所以 = (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3)，12ka 其中 q 是某个整数。这说明式(4)当 n = k 1 也成立。 由归纳法知式(4) 对所有正整数 n 成立。 ； 15362i 15806i 解： ；347280i 2 剩余类及完全剩余系 1、 证明 ， ， 是模 的一个完全剩余类。stxupv0,12,tp ssp 证明：显然对 的不同取值， 共有 个值，故只需证这样的 个值，关于模,xstsp 的两两互不同余。sp 若 1122modststsuvpvst s ，即stp121212stupu12ododststs tvvv 或 时，12u12 结论成立。2mststspvuvp 2、 若 是 个两两互质的正整数， 分别通过模 的完全剩12,km 12,kx 12,km 余类，则 12kMxx 通过模 的完全剩余系，其中 ，km imM1,2k 证明：（数学归纳法） （1） 根据本节定理 3，知 时，结论成立。2 （2） 设对整数 ，结论成立，即若 两两互质，令1k121,k ，当 分别通过模 的完全 2ksMxx x 121,km 剩余系时， 必过模s 的完全剩余系，其中 。121.km (1,2.)imMik 现增加 使 ，,(,)i(1,.)ik 令 ， ，.ikM 121.kk12.kkm 则易知 ，12(,)(,)kkm 再令 ，kxs 当 过模 的完全剩余系， 过模 的完全剩余系时，据本节定理 3， 必过模k kMx 的完全剩余系，即对 结论成立。12.mMkm 3、 （i）证明整数 中每一个整数有而且只有一种方法表示成 13,.0,1.()nHH 10.3nnxx 的形状，其中 ；反之，中每一数都 。,1(,)iin ,H且 （ii）说明应用 个特别的砝码，在天平上可以量出 1 到 H 中的任意一个斤数。 证明：（i）当 时，过模 的绝对最小完全剩余系，也就,0(,.)ixi23n 是 表示 中的 个整数，事实上，当 时，共有 个值，且两两互,H21,0ix13n 不相等，否则 1 110 103.33.n nn nxx 初等数论习题解答（第三版） 23 / 77 1 110 003()().3()| .nnnxxxx 此即 1 2 1 1()().()3| .nnnnxxx 又 的最大值是 1133.n H 最小值是 1.n 所以，结论成立。 （ii）特制 个砝码分别重 斤，把要称的物体 及取-12,3.,n 11rriiiiad 的砝码放在天平的右盘， 取 1 的砝码放在左盘，则从（i）的结论知，当 取适当的值时，ix ix 可使 之值等于你所要称的物体的斤数 。103.3.nnTxH 4、若 是 K 个两两互质的正整数， 分别过模 的完全剩余系，12,.km12,.kx12,.km 则 1212312,.,.kxxm 通过模 的完全剩余系。.k 证明：（数学归纳法） （1） 时， 分别过模 的完全剩余系时，2K12,x12, 共有 个值，且若xm12121212112(od)()(mod)xmxx ，且1221 ， ，即 时结论成立；1x2xk （2）设当 分别过模 的完全剩余系时，,k 2,km 过模 的完全剩余系。23231kxmmx 2k 因为 ，由本节定理 2 得，1(,)k 亦过模 的完全剩余系。2321)kxx km 当 分别过模 的完全剩余系时，11,kx 21, 2 有 个值，且据归纳假设，2m 若 11211kkxxmx 2 1(od)km ； 11(od)x232kxx 12()km ， ，11()x22(od)xodkxm ， ， 。2k 所以 过模 的完全剩余系。1121xmx 12k 3简化剩余系与欧拉函数 1证明定理 2：若 是 与 互质的整数，12(),ma 并且两 对模 不同余，则 是模 的一个简化剩余系。12(),a 证明： 两 对模 不同余，所以它们分别取自模 的不同剩余类，12(),ma m 又 恰是 个与 互质的整数，即它们恰取自与模 互质的全部剩余类。(), ()m 2若 是大于 1 的正整数， 是整数， ， 通过 的简化剩余系，a(,)1 则 ，其中 表示展布在 所通过的一切值上的和式。()2am 证明：由定理 3 知， 通过 的简化剩余系：m 初等数论习题解答（第三版） 25 / 77 ，其中 0 且 ，12(),ma ia(,)1im 而 （ ） 。ii1,2() 若 2，则 必是偶数，又由 ，(),)1ia 得 ，且易见 ，(,1imaiim 故 1iiiia 所以 ()12.mam 左边每一项 都存在另一项 ，ia()jii 使得 ，右边共有 对，1jim1()2m 此即 。()2a 特别地，当 m=2 时， 。1(),2am 3 （i）证明 ，p 质数。(1)p (ii) 证明 ，其中 展布在 a 的一切正整数上的和式。dada 证明：（i）因为 ，1()kk(,2) 所以 (1)p = 21()()p = (ii)设 是 a 的标准分解式，12kap 则 ，1 212()()(1)kkdappp 1) (k = 12kp =a 4若 是 k 个两两互质的正整数， 分别通过模 的简化12,m 12,k 12,km 剩余系，则 12kM 通过模 的简化剩余系，其中 。2k ,12,imMk 证明：（数学归纳法） （1） 由定理 4 知 k=2 时，结论成立； （2） 设 k-1 时结论成立，即 ， 分别1(,)ki k 121,k 过模 时，11,km 21kM 过 模的简化剩余系。 显见 ，则又由定理 4 知， 通过模 的简化剩余系，注意到：(,)1k kkmMkm121()()()kkkkkm121M 所以， 通过模 m 的简化剩余系。12k 欧拉定理 费马定理及其对循环小数的应用4 、如果今天是星期一，问从今天起再过 天是星期几？10 解：若 被 除的非负最小剩余是 ，则这一天就是星期 （当 时是星期日）107rr0 ，由费马定理得 ，A610mod7 初等数论习题解答（第三版） 27 / 77 又 10105102mod724mod664KZ10 4103157 即这一天是星期五 、求 被 除的余数。285637 解： ，1.137627 据欧拉定理，易知 36 362182mod1mod17 （）562012371 又 12350od1A 故 2 4250mod753mod18 1613746 则 由（）即得201 562 56od285613740od1 由以上计算，知 206mmA 8561237440od 、 证明下列事实但不许用定理推论：若 是质数， 是整数，则()i p12,ah 。1212ppaahh 由 证明定理推论，然后再由定理推论证明定理。()i 证明 对 应用数学归纳法： 当 时，按二项式展开即得12a12()modpphh 设 时，结论成立，即2ak112()modppkkhhp 当 时， 12121()()odppk kpkhhh 结论成立。 在 的结论中，令 ，即得：()i 12ah modpap 即定理推论成立。 进一步，设 ，则 1s 11i siip 固对任一整数 ，若 ，则由上述已证性质得：p,a 存在 ，使1modpakz1pk 故 = （ ）()12ppCl z12p 依此类推可得 1()od,pa即 1modpa 若 ，则 ,m,12.i s 1odi ipa ，定理成立。1odi map 4、证明：有理数 表成纯循环小数的充分与必要条件是有一正数 t 使得同,0,ab 余式 成立，并且使上式成立的最小正整数 t 就是循环节的长度。0t 证明： 必要性，若结论成立，则由定理 2 知（b，10）=1，i 令 t= 则据欧拉定理得 ；,b10modt 充分性，若有正数 t，满足2at 令 t 为使上式成立的最小正整数，且 =t1qb 初等数论习题解答（第三版） 29 / 77 110,taqbaq 且 。t0tt 以下参照课本 51 页的证明可得： = 即 可表成循环小数，但循环节的长度就是 t。ab 10t ab 第四章 同余式 1 基本概念及一次同余式 例 解同余式 2150mod4x 解： （12，45）=3 同余多项式有 3 个解 而原同余式为 450od1x m 4 2x 150od15 与 也一样0(od)x(4)x 所以原同余式的 3 个解是 （、）t 即 ， ， 1(m5)2(od15)30(mod15)x 1、 求下列各同余式的解 256x 179i23037 1215x 560iod5 1296x 1125m193 337 是素数， ，原同余式有唯一解。i256,371 先解同余式 256x 120mod 由辗转相除法，得 5643791 上述同余式的解是 10odx 原同余式的解是8m （1215，2755）=5，故先解 i 243x 112 2305mod51 同 的方法的得其解是i 20od51x 原同余式的解是,73,8240mod75 (1296， 1935)=9，故原同余式有 9 个解。i 由 144x 125 得2305mod1580od215x 原同余式的解是 293,8.xtt 2求联立同余式 的解。40(od14)98myx 解：据同余式的有关性质， 490(od13)284xy29(3)71od4y 为所求的解。()4mod13y()2m3xy 3(i)设 是正整数， 证明(,)1a ()1mxb 初等数论习题解答（第三版） 31 / 77 是同余式 的解(mod)axb (ii)设 是质数， ，证明p0p1()(1)(od!aax 是同余式 的解odb 证明: (i) ， 有唯一解(,)1am()axbm 而据欧拉定理，得 ，() ()1()1odod)mmxbaa 即 是 的解()xb (ii) 即 有唯一解0,)1p()p 又 个连续整数之积必被 所整除，a!a 故可令 1()apbk 则 ()1)!p1 2()( (mod)a aabp 即 2()!)!odbkpmodkp 即 1()(1)(!aax 是 的解b 设 p 是 素 数 ， 0 2）的原根是存在的，试证对模 m 的任一原根来说， 的指标总是1 1()2 证明：模 m 的原根存在，故 m=4， 或 p2 设 为模 m 的一个原根，则 g()1od)mg 从而 11()()220 若 m=4， ，则模 m 有且只有一个原根 3， i4 ， 13(od) 故 的指标为2 若 ， 为奇质数，则由 知1mp 或90 1()2|g 但二者不能同时成立，否则 ，矛盾! 11()()22|mpg 若 又由（*）知 1()2|,|mpg1()2,m()| （mod m） ，与 的指数为 矛盾。 1()2mg()m 从而 ，从而|p(),g 1()2|12|p （mod m） 1()2m 故-1 的指标为 。() 若 ， 为 的原根，则 为奇数()ipg2g 类似于 的讨论，我们有()i ，|p 1()2mg1()2|mpg 从而 1()2| 从而 （mod m） 1()2mg 故-1 的指标为 。 5、设 ， 是模 的两个原根，试证：1 （mod ） ；()i11gndi() （mod ） 。1gandam 证明： 由指标的定义知：()i （mod m）1gind 两边对原根 取指标：1 （mod ） 11gindg() 故 （mod ）1gii 由指标的定义知：() （mod m）1ginda 两边对原根 取指标： （mod ）1gindag() 故 （mod ） 。 （证毕）1gii 第九章 数论函数 1 可乘函数 1设 是一个可乘函数，证明 也是一个可乘函数由此说明()fx()()dxFf 是可乘函数,sa 证明：首先我们证明：设 ，若 跑过 的全部因子， 跑过 的全部因子，则12(,)x1 2dx 初等数论习题解答（第三版） 59 / 77 跑过 的全部因子，事实上，因为 ，故 ，且当12dmn12,dx12dx ， 时，由于 ，得 ，反之任给 ，,x1212,d()12dx 由于 ，设 ， ，显然 因此12()()x2()x1212,x121212,dxdxFff 12() 1212()dxdxffFx 故 为一个可乘函数 (此为 65 页)Fx 若 ，它为可乘函数 ，且 f()()dafS 若 ，它为可乘函数，且 ()1xF 故 为可乘函数,Sa 2 设 是一个定义在一切正态数的函数，并且 是一个可乘函数，证明()fx ()()dxFf 是可乘函数f 证明：反证，假设 不是可乘函数，则存在一对正态数 ，使得()fx ,(,)1mn ，于是我们可以选择这样一对 ，使得 最小若 ，则()(fmnf , n ，即 ，又 ， 为可乘函数，故有1)(1)f1()()dFfa()Fx 矛盾！(fF 若 ，则对所有正态数对 ，有mn1a,b ()=1,a0， 0，则 对模 的指数是( )xmabxm A B C D无法确定a 19 ， 均为可乘函数，则( )fg A 为可乘函数； B 为可乘函数f fag C 为可乘函数； D 为可乘函数fagf 20设 为茂陛乌斯函数，则有( )不成立 A B C D112190 二填空题：（每小题 1 分，共 10 分） 21 3 在 45 中的最高次 n _；! 22 多元一次不定方程： ，其中 ， ， ，N 均为整数，12naxaxN 1a2na ，有整数解的充分必要条件是_；2n 23有理数 ， ， ，能表成纯循环小数的充分必要条件是ab0,b _； 24 设 为一次同余式 ， 的一个解，则它的所0modxmodaxa0odm 初等数论习题解答（第三版） 67 / 77 有解为_； 25 威尔生（wilson）定理：_； 26 勒让德符号 =_；5031 27 若 ，则 是模 的平方剩余的充分必要条件是_(欧拉判别条件)；,apap 28 在模 的简化剩余系中，原根的个数是_；m 29 设 ， 为模 的一个原根，则模 的一个原根为_；1g2p 30 _。48 三简答题：（5 分题4 题20 分） 31命题“任意奇数的平方减 1 是 8 的倍数”对吗？说明理由。 32 “若 ， 通过模 的简化剩余系，则 也通过模 的简化剩余系” 这命题是否正,1amxaxm 确？正确请证明，不正确请举反例。 33求模 17 的简化剩余系中平方剩余与平方非剩余。 34设 为 的标准分解式，记 为 的正因数的和， 为 的正因数12kp aSa 的个数，则 ？ ？ 为什么？S 四计算题。 （7 分题4 题 28 分） 35 求不定方程 6x+93y=75 的一切整数解。 36 解同余方程组 1mod53627xyz 37解同余式 11(mod125)2x 38求模 13 的所有原根。 五、证明题：（7 分/题2 题 =14 分） 39、试证： ， （x，y）=1 y 是偶数的整数解可写成：22xz ()xaba2b 这里 ， ，并且 一为奇数，一为偶数。0,1 40、设 a 为正整数，试证： | |()()dada 其中 表