《初等数论闵嗣鹤、严士健》第三版习题解答

1、第一章 整数的可除性§1 整除的概念·带余除法1证明定理3定理3 假设都是得倍数，是任意n个整数，那么是得倍数证明： 都是的倍数。 存在个整数使 又是任意个整数即是的整数2证明 证明 又，是连续的三个整数故 从而可知 3假设是形如x，y是任意整数，a，b是两不全为零的整数的数中最小整数，那么证： 不全为在整数集合中存在正整数，因而有形如的最小整数，由带余除法有那么，由是中的最小整数知 为任意整数 又有， 故4假设a，b是任意二整数，且，证明：存在两个整数s，t使得成立，并且当b是奇数时，s，t是唯一存在的当b是偶数时结果如何？证：作序列那么必在此序列的某两项之间即存在一个整

2、数，使成立当为偶数时，假设那么令，那么有 假设 那么令，那么同样有当为奇数时，假设那么令，那么有假设 ，那么令，那么同样有，综上所述，存在性得证下证唯一性当为奇数时，设那么而 矛盾 故当为偶数时，不唯一，举例如下：此时为整数§2 最大公因数与辗转相除法推论4.1 a，b的公因数与a，b的因数相同证：设是a，b的任一公因数，|a，|b由带余除法|， |，, |,即是的因数。反过来|且|，假设那么，所以的因数都是的公因数，从而的公因数与的因数相同。2证明：见本书P2，P3第3题证明。3应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际

3、算出76501，9719解：有§1习题4知：使。，使如此类推知： 且而b是一个有限数，使，存在其求法为：4证明本节1式中的证：由P3§1习题4知在1式中有 ，而 ， ，即§3 整除的进一步性质及最小公倍数1证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件证明 必要性。假设，那么由推论知存在两个整数s，t满足：，充分性。假设存在整数s，t使as+bt=1，那么a，b不全为0。又因为，所以 即。又，2证明定理3定理3 证：设，那么又设那么。反之假设，那么，从而，即=3设 1是一个整数系数多项式且，都不是零，那么1的根只能是以的因数作分子以为分母的既约

4、分数，并由此推出不是有理数证：设1的任一有理根为，。那么 2由，所以q整除上式的右端，所以，又，所以；又由2有因为p整除上式的右端，所以 ，所以故1的有理根为，且。假设为有理数，次方程为整系数方程，那么由上述结论，可知其有有理根只能是，这与为其有理根矛盾。故为无理数。另证，设为有理数=，那么但由知，矛盾，故不是有理数。§4 质数·算术根本定理1试造不超过100的质数表解：用Eratosthenes筛选法1算出a210内的质数为：2，3，5，73划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数排列如下： 1 2 3 4 5 6 7 8 9 1011 12

5、 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100解：因为8|848，所以，又8|856，所以8|B，又4|32，所以4|C，又9|3+

6、2+3+4+3+3，所以9|D，又9|3+5+9+3+7，所以9|E，又所以；同理有。3证明推论3.3并推广到n个正整数的情形推论3.3 设a，b是任意两个正整数，且，那么，其中，证：， ，. ，又显然 ，同理可得，推广设,(其中为质数为任意n个正整数)， 那么4应用推论3.3证明§3的定理4ii证：设，其中p1, p2, L, pk是互不相同的素数，ai，bi1 £ i £ k都是非负整数，有由此知(a, b)a, b =ab；从而有假设是质数n>1，那么n是2的方幂证：反证法设为奇数，那么 ， 为合数矛盾，故一定为的方幂§5 函数x,x及其在数

7、论中的一个应用1求30！的标准分解式解：30内的素数为2，3，5，7，11，13，17，19，23，29， 2设n是任一正整数，a是实数，证明：(i) (ii) 证：(i)设.那么由性质II知,所以 ,所以，所以，又在与+之间只有唯一整数，所以 (ii) 证法一设,那么当时, ;当时,;证法二令,是以为周期的函数。又当，即。评注：证一充分表达了 常规方法的特点，而证二那么表现了较高的技巧。3设，是任意二实数，证明：(i) 或(ii) 证明：i由高斯函数x的定义有。那么 当 当 故 ii设，那么有 下面分两个区间讨论：假设，那么，所以，所以假设，那么，所以。所以ii证法2由于，对称，不妨设4.

8、(i) 设函数在闭区间上是连续的，并且非负，证明:和式表示平面区域，内的整点整数坐标的点的个数.(ii) 设p，q是两个互质的单正整数，证明：(iii) 设，T 是区域 内的整点数，证明：(iv) 设，T 是区域， 内的整点数，证明：证明：(略) 5. 设任一正整数，且，p 是质数，证明：在的标准分解式中，质因数p的指数是其中.证明：在的标准分解式中，质因数p的指数有限，即，所以而第二章 不定方程§21 习题1、解以下不定方程 解： 原方程等价于： 显然它有一个整数解 ， 故一般解为 原方程等价于： 显然它有一个整数解 故一般解为 2、把100分成两份，使一份可被整除，一份可被整除。

9、解：依题意 即求 的正整数解，解得 一般解是： 但除 外无其他正整数解，故有且只有 3、证明：二元一次不定方程 的非负整数解为 或 证明：当时，原方程没有整数解，而 故命题正确 当时，原方程有且只有一个非负整数解 而 因为 所以 原方程有整数解 其中，由于，故中一正一负，可设 原方程的一般解是： 要求，仅当 是整数时，才能取 ，否那么 故这个不等式的整数解个数 是 ：当是整数时 因而 当 不是整数时 因而 所以 证明2：二元一次不定方程ax + by = N的一切整数解为，tÎZ，于是由x ³ 0，y ³ 0得，但区间的长度是，故此区间内的整数个数为+ 1。：4、

10、证明：二元一次不定方程 ，当 时有非负整数解， 那么不然。证明：先证后一点，当 时，原方程有非负整数解 那么，这是不可能的。次证，当N>ab-a-b时，因(a，b)=1，故原方程有整数解x，y，一般解是要求x-bt0，y会证明存在满足这个不等式的整数可取使于是对于这个有：而这就证明了当时，原方程有非负整数解1证明定理2推论。推论 单位圆周上座标都是有理数的点称为有理点，可以写成的形式，其中a与b是不全为零的整数。证明：设有理数m ¹ 0满足方程x2 + y2 = 1，即l2 + n2 = m2，于是得l = ±2abd，n = ±(a2 - b2)d，m =

11、 ±(a2 + b2)d或l = ±(a2 - b2)d，m = ±2abd，m = ±(a2 + b2)d，由此得(x, y) =。反之，代入方程x2 + y2 = 1即知这样的点在单位圆周上。2求出不定方程的一切正整数解的公式。解：设不定方程有解那么(1)3/z-x或3/z+x因为或3/z+x以下不妨设， 设 与矛盾!这样而， ， 即 假设由引理可设从而 ， 为证得为整数， 必须有a ， b均为奇数，且假设设，其中为一奇一偶，且有4解不定方程：x2 + 3y2 = z2，x > 0，y > 0，z > 0，(x, y ) = 1。解

12、：设(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 > 0，(a, b ) = 1，3b，a, b同为奇数； () 当d = 2：x = |b2 - 3a2|，y = 2ab，z = b2 + 3a2，a > 0，b > 0，(a, b ) = 1，3b，a, b一奇一偶。反之，易验证()或

13、()是原不定方程的解，且x > 0，y > 0，z > 0，(x, y) = 1。3证明不等式方程的一切正整数解可以写成公式: ，其中 证明:由定理1知道原方程的解是， 且c， d为一奇一偶，其中， 且a， b为一奇一偶所以，是原方程的正整数解，原方程正整数的解有: ，6求方程x2 + y2 = z4的满足(x, y ) = 1，2½x的正整数解。解：设x，y，z是x2 + y2 = z4的满足(x, y) = 1，2½x的正整数解，那么x = 2ab，y = a2 - b2，z2 = a2 + b2，a > b > 0，(a, b) = 1，

14、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，2½x。其中正负号可任意选取第三章

15、同余1同余的概念及其根本性质1、 证明i假设(modm)xy(modm)、i=1，2，、，k那么(modm)特别地，假设modm，i=0，1，那么modm(ii)假设ab(modm)，kiii假设ab(modm)，d是a，b及m的任一正公因数，那么(iv)假设ab(modm)， 那么ab(modd)证明 ：i据性质戊，由得进一步，那么最后据性质丁，可得：modm(ii) 据定理1，ab(modm)又据定理1，即得iii据定理1， ab(modm) 即a-b=ms(sz)，即仍据定理1，立得(iv) 据定理1， ab(modm)又故2、设正整数试证11整除的充分且必要条件是11整除证明 ：由上题

16、(i)的特殊情形立得3找出整数能被37，101整除有判別条件来。解：故正整数立得故设正整数，立得4、证明证明： 即5、假设是任一单数，那么，证明：数学归纳法设 1时， 结论成立。 2设时，结论成立，即： ，而 故时，结论也成立；时，结论也成立。证明：假设2a，n是正整数，那么º 1 (mod 2n + 2)。 (4)设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 +

17、2，其中qÎZ，所以= (1 + q2k + 2)2 = 1 + q ¢2k + 3 º 1 (mod 2k + 3)，其中q ¢是某个整数。这说明式(4)当n = k + 1也成立。由归纳法知式(4)对所有正整数n成立。； 解：；§2 剩余类及完全剩余系1、 证明，是模的一个完全剩余类。证明：显然对的不同取值，共有个值，故只需证这样的个值，关于模的两两互不同余。假设，即或时， 结论成立。2、 假设是个两两互质的正整数，分别通过模的完全剩余类，那么 通过模的完全剩余系，其中，证明：数学归纳法（1） 根据本节定理3，知时，结论成立。（2） 设对整

18、数，结论成立，即假设两两互质，令，当分别通过模的完全剩余系时，必过模的完全剩余系，其中。现增加使 ，令，那么易知，再令，当过模的完全剩余系，过模的完全剩余系时，据本节定理3，必过模的完全剩余系，即对结论成立。3、i证明整数中每一个整数有而且只有一种方法表示成的形状，其中；反之，中每一数都。 ii说明应用个特别的砝码，在天平上可以量出1到H中的任意一个斤数。证明：i当时，过模的绝对最小完全剩余系，也就是表示中的个整数，事实上，当时，共有个值，且两两互不相等，否那么此即又的最大值是最小值是所以，结论成立。ii特制个砝码分别重斤，把要称的物体及取-1的砝码放在天平的右盘，取1的砝码放在左盘，那么从i

19、的结论知，当取适当的值时，可使之值等于你所要称的物体的斤数。4、假设是K个两两互质的正整数，分别过模的完全剩余系，那么通过模的完全剩余系。证明：数学归纳法1时，分别过模的完全剩余系时，共有个值，且假设，且，即时结论成立；2设当分别过模的完全剩余系时，过模的完全剩余系。因为，由本节定理2得，亦过模的完全剩余系。当分别过模的完全剩余系时，2有个值，且据归纳假设，假设； ，。所以过模的完全剩余系。3简化剩余系与欧拉函数1证明定理2：假设是与互质的整数，并且两对模不同余，那么是模的一个简化剩余系。证明： 两对模不同余，所以它们分别取自模的不同剩余类，又恰是个与互质的整数，即它们恰取自与模互质的全部剩余

20、类。2假设是大于1的正整数，是整数，通过的简化剩余系，那么，其中表示展布在所通过的一切值上的和式。证明：由定理3知，通过的简化剩余系：，其中0且，而。假设2，那么必是偶数，又由，得，且易见，故所以左边每一项都存在另一项，使得，右边共有对，此即。特别地，当m=2时，。3i证明，p质数。(ii) 证明，其中展布在a的一切正整数上的和式。证明：i因为，所以 = =(ii)设是a的标准分解式，那么， = =a4假设是k个两两互质的正整数， 分别通过模的简化剩余系，那么 通过模的简化剩余系，其中。证明：数学归纳法（1） 由定理4知k=2时，结论成立；（2） 设k-1时结论成立，即，分别过模时，过模的简化

21、剩余系。显见，那么又由定理4知，通过模的简化剩余系，注意到：所以，通过模m的简化剩余系。欧拉定理费马定理及其对循环小数的应用、如果今天是星期一，问从今天起再过天是星期几？解：假设被除的非负最小剩余是，那么这一天就是星期当时是星期日，由费马定理得，又即这一天是星期五、求被除的余数。解：，据欧拉定理，易知又故那么由即得由以上计算，知、证明以下事实但不许用定理推论：假设是质数，是整数，那么。由证明定理推论，然后再由定理推论证明定理。证明对应用数学归纳法：当时，按二项式展开即得设时，结论成立，即当时，结论成立。在的结论中，令，即得：即定理推论成立。进一步，设，那么固对任一整数，假设，那么由上述已证性质

22、得：存在，使故=依此类推可得假设，那么 ，定理成立。4、证明：有理数表成纯循环小数的充分与必要条件是有一正数t使得同余式成立，并且使上式成立的最小正整数t就是循环节的长度。证明：必要性，假设结论成立，那么由定理2知b，10=1，令t=那么据欧拉定理得；充分性，假设有正数t，满足令t为使上式成立的最小正整数，且=且。以下参照课本51页的证明可得：=即可表成循环小数，但循环节的长度就是t。第四章 同余式 1 根本概念及一次同余式例 解同余式 解：12，45= 同余多项式有3个解 而原同余式为 4 与也一样所以原同余式的3个解是 、即，1、 求以下各同余式的解 256x179 1215x560129

23、6x1125337是素数， ，原同余式有唯一解。先解同余式256x1由辗转相除法，得上述同余式的解是原同余式的解是1215，2755=5，故先解 243x112 同的方法的得其解是原同余式的解是(1296，1935)=9，故原同余式有9个解。 由144x125得原同余式的解是2求联立同余式的解。解：据同余式的有关性质，为所求的解。3(i)设是正整数，证明 是同余式 的解(ii)设是质数，证明是同余式的解证明: (i) ， 有唯一解而据欧拉定理，得 ， 即 是的解(ii) 即有唯一解又 个连续整数之积必被所整除，故可令 那么即即 是的解设p是素数，0 < a < p，证明：(mod

24、p)。是同余方程ax º b (mod p)的解。解：首先易知是整数，又由(a, p) = 1知方程ax º b (mod p)解唯一，故只须将(mod p)代入ax º b (mod p)验证它是同余方程的解即可。4设是正整数，是实数，证明同余式有解证明: 因 故同余式 必有解，(i) 假设 ，那么结论成立;(ii) 假设，令，那么又假设 那么由 ，结论成立假设 令 那么 又假设 那么由即 故 结论成立。假设又令 那么 重复上述讨论：即假设 那么结论成立， 假设又令 例解同余方程组解：互质，故原方程组对模有唯一解即根据孙子定理方程组的解是注意到 故有限步后，必有

25、 其中即结论成立。孙子定理试解以下各题：（i） 十一数余三，七二数余二，十三数余一，问本数。（ii） 二数余一，五数余二，七数余三，九数余四，问本数。 杨辉：续古摘奇算法1275。解：i依题意得那么据孙子定理，上述方程组有唯一解由故原方程组的解是(ii)依题意得2、i设 是三个正整数，证明： ii设 证明：同余式组 1有解的充分与必要条件是在有解的情况下，适合1的一切整数可由下式求出：其中是适合的一个整数。应用证明同余式组 有解的充分与必要条件是，并且有解的情况下，适合的一切整数可由下式求出：其中是适合的一个整数。证明： 即 设有解，即故此得，必要性成立；反之，设即那么由§1定理，知

26、方程必有解，设其解为，即令那么易见：且即有解，充分性得证。进一步，假设有解，那么即是的公倍数，当然也是的倍数，故假设是的一个解，那么的任一解必满足。假设同余式组有解，那么 也有解。从而由知必有，必要性成立。下证充分性。首先，推，用归纳法易证：又由知时，充分性也成立；现设同余式组 有解，即。设；又由条件知，而，从而，所以，即，又由，那么同余式组，必有解 显然，即就是同余式组的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。§3 高次同余式的解数及解法1、 解同余式。解：原同余式等价于 据孙子定理，可得故原同余式共有6个解是：2、 解同余式解： 故原同余式等价于1） 先解即 得再解

27、即 设 而由孙子定理设即原四条式有4个解是§4质数模的同余式补充例子：1解同余方程：() 3x11 + 2x8 + 5x4 - 1 º 0 (mod 7)；() 4x20 + 3x12 + 2x7 + 3x - 2 º 0 (mod 5)。解：() 原同余方程等价于3x5 + 5x4 + 2x2 - 1 º 0 (mod 7)，用x = 0，±1，±2，±3代入知后者无解； () 原同余方程等价于2x4 + 2x3 + 3x - 2 º 0 (mod 5)，将x = 0，±1，±2 代入，知后者

28、有解x º ±1 (mod 5)。2判定() 2x3 - x2 + 3x - 1 º 0 (mod 5)是否有三个解；() x6 + 2x5 - 4x2 + 3 º 0 (mod 5)是否有六个解？解：() 2x3 - x2 + 3x - 1 º 0 (mod 5)等价于x3 - 3x2 + 4x - 3 º 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系数不都是5的倍数，故原方程没有三个

29、解； () 因为这是对模5的同余方程，故原方程不可能有六个解。定理5 假设p是素数，n½p - 1，pa那么x n º a (mod p) (14)有解的充要条件是º1 (mod p)。 (15)假设有解，那么解数为n。证明 必要性 假设方程(14)有解x0，那么px0，由Fermat定理，得到= x0p - 1 º1 (mod p)。充分性 假设式(15)成立，那么其中P(x)是关于x的整系数多项式。由定理4可知同余方程(14)有n个解。证毕。1、 设， ， 证明同余式 有解的充分必要条件是，并且在有解的情况下就有个解。证明：设那么但那么由 可得。它有

30、个解。 令那么无多于个解，而 恰有个解，必有个解。2设n是整数，a，m=1，且同余式有一解，证明这个同余式的一切解可以表成 其中y是同余式的解。证明：设均是的解， 那么， a，m=1 ， ，m= (，m) = 1 那么由第三章定理33知，必存在y，使 ， 故原同余式的任一解可表示为而y满足3设(a, m) = 1，k与m是正整数，又设x0k º a (mod m)，证明同余方程xk º a(mod m)的一切解x都可以表示成x º yx0 (mod m)，其中y满足同余方程yk º 1 (mod m)。解：设x1是xk º a(mod m)的任

31、意一个解，那么一次同余方程yx0 º x1 (mod m)有解y，再由yka º ykx0k º (yx0)k º x1k º a (mod m)得yk º 1 (mod m)，即x1可以表示成x º yx0 (mod m)，其中y满足同余方程yk º 1 (mod m)；反之，易知如此形式的x是xk º a(mod m)的解。第五章 二次同余式与平方剩余§1 一般二次同余式1、 在同余式中，假设，试求出它的一切解来。解：假设，那么，上同余式即为从而，即有。易见，当为偶数时，那么，上同余式有解：

32、，共有个解当为奇数时，上同余式有解：，共有个解。2、证明：同余式 有解的充分必要条件是 有解，并且前一同余式的一切解可由后一同余式的解导出。证明：因，故用乘后再配方，即得仍记为，即有由以上讨论即知假设为的解，那么为的解，必要性得证。反之，假设有一解，即有：由于，故有解即有：即有：由，即有：即为的解，充分性得证。由充分性的讨论即知的解可由的解导出。§2 单质数的平方剩余与平方非剩余1、 求出模的平方剩余与平方非剩余。解：，由书中定理2知，模的简化剩余系中个平方剩余分别与序列例2试判断下述同余方程是否是有解。 1 2 3中之一数同余，而 故模37的平方剩余为： 1，3，4，7，9，10，

33、11，12，16，21，25，26，27，30，33，34，36而其它的18个数为模37的平方非剩余： 2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，352 应用前几章的结果证明:模的简化剩余系中一定有平方剩余及平方非剩余存在， 证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。 应用、证明：模的简化剩余系中平方剩余与平方非剩余的个数各为。证明：因为1为模的简化剩余系中的平方剩余。假设模的简化剩余系中均为平方剩余，考虑模的绝对最小简化剩余系：它们的平方为模下的个数： 由假设模的简化剩余系中任一个数与上个数同余，而模的简化剩

34、余系中有个数，故必有两个互相同余，矛盾。从而必有平方非剩余存在。假设为平方剩余，那么故从而也为平方剩余。假设为平方剩余，为平方非剩余，那么故从而为平方非剩余。设为模的简化剩余系中的平方剩余；为模的简化剩余系中的平方非剩余。由知，为平方非剩余，显然互不同余。故反之，由为平方剩余知故，得证。3证明：同余式，的解是 ，其中 证明：假设有解，那么有解， 设其解是：，即有： ，令而 ， 为整数由此两式即得： 两式相乘得： 取使得： 那么 故其解为 4证明同余式 的解是 证明：首先我们证明对任意： 有下式： 因为 ，于是 因此由威尔生定理得： 其次由，可令 ，代入上式即有 故原同余式的解为 §3

35、 勒让得符号1用本节方法判断以下同余式是否有解 其中503，563，769，1013都是质数 解：，有解。，有解。 ，有解。2、求出以为平方剩余的质数的一般表达式；以为平方非剩余的质数的一般表达式。解：为模平方剩余时，必有，必有，故，必有，故为模平方非剩余时，必有，必有，故，必有，故3、设是正整数，及都是质数，说明由此证明：。证明：当时，由本节定理1的推论知为平方剩余，应用欧拉判别条件即有由，即得出而都是形如的素数，并且，所以。§4 前节定理的证明1、 求以为平方剩余的质数的一般表达式，什么质数以为平方非剩余？解：由互反律 因此当它们同为或同时为时，一为，一为时，显然，当为偶数，而时

36、，当是奇数，即时，。再因为是奇质数，关于模我们有或，当时，当时，这样为平方剩余时，为下方程组的解或由孙子定理，即可知或，立即当时，为平方剩余。为平方非剩余时，为下方程组的解或由孙子定理，即可知或，立即当时，为平方非剩余。因为当为偶数，或为奇数，时，即或时，为平方剩余，类似或，为平方非剩余。2、求以为最小平方非剩余的质数的一般表达式。解：由上题知以为平方非剩余的质数满足：又由为模的最小平方非剩余，故从而§3推证满足的素数形如，其中只有满足故或时，为它的最小平方非剩余。§5 雅可比符号1、 判断§3习题1所列各同余式是否有解。略2、 求出以下同余式的解数：，其中是一个

37、质数。解：，故故，即的解数为0 ，故解数为23 在有解的情况下，应用定理1，求同余式，的解。在有解的情况下，应用 §2 定理1及§3定理1的推论，求同余式，的解。解：同余式有解，故 由知故即为原同余式的解。 由知，故故因此或假设前式成立，那末 即 假设那么原同余式的解是 即 为原同余式的解。 假设后式成立，那末 由§3定理1的推论知，2是模p的平方剩余，即于是： 假设那么原同余式的解是故为原同余式的解§6 合数模的情形1. 解同余式 ，解：从同余式 得令代入得出从而即有故，再令代入 得出 ， 即从而 故 所以 为所给同余式的解从而所有的解为：，故有四解记

38、代入，即有：解得记，代入即有：，解得：又记，代入即有，解得: 故为其一解其余三解为： 2证明同余式与同余式等价，应用举出一个求同余式的一切解的方法。证明：显然 记有解，等价于方程组有解易见的解为的解为的解为或二者不能同时成立，否那么矛盾故它有两个解，联立方程组即可求出一切解。第六章 原根与指标1. 设p是单质数，a是大于1的整数，证明:(i)的奇质数q是a-1的因数或是形如2px+1的整数，其中x是整数(ii) 的单质因数是a+1的因数或是形如2px+1的整数，其中x是整数证明(i)设 那么设a对模q的质数是 是质数 从而或p假设，那么，故;假设，而，q-1为偶数，记q-1=2x，那么，又假设

39、故q=2px+1得证。(ii)设q为的奇质因数，那么从而，从而a对模q的指数故，2，p，2p之一假设，那么，从而 即有，不可能，故假设，那么，而(否那么) 故假设，那么，而有，不可能假设，那么由，q12m记mpx，那么q2px+1，得证2. 设对模m的指数是，试证对模m的指数是证明：设对模m的指数为，那么 而，股反之故，从而=得证例1 求1，2，3，4，5，6对模7的指数。根据定义1直接计算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，d7(4) = 3，d7(5) = 6，d7(6) = 2。例1中的结果可列表如下：a123456d7(a)136362这样的表称为指数表。

40、这个表就是模7的指数表。下面是模10的指数表：a1379d10(a)14421写出模11的指数表。解：经计算得d11(1) = 1，d11(2) = 10，d11(3) = 5，d11(4) = 5，d11(5) = 5，d11(6) = 10，d11(7) = 10，d11(8) = 10，d11(9) = 5，d11(10) = 2，列表得a12345678910d11(a)110555101010522求模14的全部原根。解：x º 3，5 (mod 14)是模14的全部原根。1求模29的最小正原根。解：因j(29) = 28 = 22×7，由知2是模29的最小正原根

41、。2分别求模293和模2×293的原根。解：由2是模29的原根及229 - 1 = 228 = 2281 (mod 292)知2是模293的原根；由2是模293的原根及2是偶数知2 + 293是模2×293的原根。3解同余方程：x12 º 16 (mod 17)。解：易得3是模17的原根，3ii = 0, 1, 2, L, 15构成模17的简化剩余系，列表为i 0 1 2 3 4 5 6 73i (mod 17) 1 3 9 10 13 5 15 11i 8 9 10 11 12 13 14 153i (mod 17) 16 14 8 7 4 12 2 6由上表知

42、38 º 16 (mod 17)，设x º 5 y (mod 17)，那么12y º 8 (mod 16)，由此解得y1 º 2，y2 º 6，y3 º 10，y4 º 14 (mod 16)，查上表得x1 º 9，x2 º 15，x3 º 8，x4 º 2 (mod 17)。3 指标及n次剩余1设 是的一切不同的质因数，证明g是模m的一个原根的充要条件是g对模m的次非剩余。 证明：必要性，设g为模m的一个原根 由2 Th5 知 假设g为模m的次剩余，那么存在，使得 又由欧拉定理 故

43、，矛盾！充分性，假设g不为模m的一个原根，由2 Th5 知存在，使得： 设为模m的一个原根，那么对上式两边关于取指标： 记 ，那么由指标的定义即有： 故 即为同余式 的解从而g为次剩余，矛盾。2证明10是模17及模257质数的原根，并由此证明把化成循环小数时，循环节的长度分别是16及256证明：，它的有且只有质因子2，而 从而10不是模17的平方剩余，由上题知10是模17的原根。，由且仅有质因子2，而故同上理10也是模257的原根。由3§4的证明可知，的循环节的长度，t，这是10关于模17，模257的指数，从而 t=16，256 证毕3试利用指标表解同余式解：同余式等价于：查表知，故

44、： 由于，故上式由 5个解，解之得：查表知：原同余式的5个解为： 4设模mm>2的原根是存在的，试证对模m的任一原根来说，的指标总是证明：模m的原根存在，故m=4，或 设为模m的一个原根，那么 从而 假设m=4，那么模m有且只有一个原根3， ， 故的指标为假设，为奇质数，那么由知或但二者不能同时成立，否那么，矛盾!假设又由*知 mod m，与的指数为矛盾。从而，从而 mod m故-1的指标为。 假设，为的原根，那么为奇数 类似于的讨论，我们有，从而 从而 mod m故-1的指标为。5、设，是模的两个原根，试证： mod ； mod 。证明：由指标的定义知： mod m两边对原根取指标：

45、mod 故 mod 由指标的定义知： mod m两边对原根取指标： mod 故 mod 。 证毕第九章数论函数§1 可乘函数1设是一个可乘函数，证明也是一个可乘函数由此说明是可乘函数证明：首先我们证明：设，假设跑过的全部因子，跑过的全部因子，那么跑过的全部因子，事实上，因为，故，且当，时，由于，得，反之任给，由于，设，显然因此故为一个可乘函数(此为65页)假设，它为可乘函数，且假设，它为可乘函数，且故为可乘函数2设是一个定义在一切正态数的函数，并且是一个可乘函数，证明是可乘函数证明：反证，假设不是可乘函数，那么存在一对正态数，使得，于是我们可以选择这样一对，使得最小假设，那么，即，又，为可乘函数，故有矛盾！假设，那么对所有正态数对，有 于是有： = =因为，故此与 为可乘函数矛盾！3证明：证明：首先易证，假设d为的正约数，那么a的完全剩余系中与的最大公约数是d的个数为。其次，假设为的所有正约数。那么也是的所有正约数，于是 最后，在的完