《初等数论(闵嗣鹤、严士健)》习题解答2012完整版[1].doc

初等数论习题解答（修改版）（茂名学院 WeiXLI）第一章 整数的可除性1 整除的概念带余除法1证明定理3定理3 若都是得倍数，是任意n个整数，则是得倍数证明： 都是的倍数。 存在个整数使 又是任意个整数即是的整数2证明 证明 又，是连续的三个整数故 从而可知 3若是形如（x，y是任意整数，a，b是两不全为零的整数）的数中最小整数，则证： 不全为在整数集合中存在正整数，因而有形如的最小整数，由带余除法有则，由是中的最小整数知 （为任意整数） 又有， 故4若a，b是任意二整数，且，证明：存在两个整数s，t使得成立，并且当b是奇数时，s，t是唯一存在的当b是偶数时结果如何？证：作序列则必在此序列的某两项之间即存在一个整数，使成立当为偶数时，若则令，则有 若 则令，则同样有当为奇数时，若则令，则有若 ，则令，则同样有，综上所述，存在性得证下证唯一性当为奇数时，设则而 矛盾 故当为偶数时，不唯一，举例如下：此时为整数2 最大公因数与辗转相除法1证明推论4.1推论4.1 a，b的公因数与（a，b）的因数相同证：设是a，b的任一公因数，|a，|b由带余除法|， |，, |,即是的因数。反过来|且|，若则，所以的因数都是的公因数，从而的公因数与的因数相同。2证明：见本书P2，P3第3题证明。3应用1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）解：有1习题4知：使。，使如此类推知： 且而b是一个有限数，使，存在其求法为：4证明本节（1）式中的证：由P31习题4知在（1）式中有 ，而 ， ，即3 整除的进一步性质及最小公倍数1证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件证明 必要性。若，则由推论1.1知存在两个整数s，t满足：，充分性。若存在整数s，t使as+bt=1，则a，b不全为0。又因为，所以 即。又，2证明定理3定理3 证：设，则又设则。反之若，则，从而，即=3设 （1）是一个整数系数多项式且，都不是零，则（1）的根只能是以的因数作分子以为分母的既约分数，并由此推出不是有理数证：设（1）的任一有理根为，。则 （2）由，所以q整除上式的右端，所以，又，所以；又由（2）有因为p整除上式的右端，所以 ，所以故（1）的有理根为，且。假设为有理数，次方程为整系数方程，则由上述结论，可知其有有理根只能是，这与为其有理根矛盾。故为无理数。另证，设为有理数=，则但由知，矛盾，故不是有理数。4 质数算术基本定理1试造不超过100的质数表解：用Eratosthenes筛选法（1）算出a（2）10内的质数为：2，3，5，7（3）划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数排列如下： 1 2 3 4 5 6 7 8 9 1011 12 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 1002求82798848及81057226635000的标准式解：因为8|848，所以，又8|856，所以8|B，又4|32，所以4|C，又9|（3+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的定理4（ii）证：设，其中p1, p2, L, pk是互不相同的素数，ai，bi（1 i k）都是非负整数，有由此知(a, b)a, b =ab；从而有若是质数（n1），则n是2的方幂证：（反证法）设为奇数），则 ， 为合数矛盾，故一定为的方幂5 函数x,x及其在数论中的一个应用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. (i) 设函数f(x)在闭区间上是连续的，并且非负，证明:和式表示平面区域，内的整点（整数坐标的点）的个数.(ii) 设p，q是两个互质的单正整数，证明：(iii) 设r0，T 是区域 内的整点数，证明：(iv) 设n0，T 是区域 x0，y0， 内的整点数，证明：证明：(略) 5. 设任一正整数，且，p 是质数，证明：在n!的标准分解式中，质因数p的指数是其中.证明：在n!的标准分解式中，质因数p的指数有限，即，所以而第二章 不定方程21 习题1、解下列不定方程 解： 原方程等价于： 显然它有一个整数解 ， 故一般解为 原方程等价于： 显然它有一个整数解 故一般解为 2、把100分成两份，使一份可被整除，一份可被整除。解：依题意 即求 的正整数解，解得 一般解是： 但除 外无其他正整数解，故有且只有 3、证明：二元一次不定方程 的非负整数解为 或 证明：当时，原方程没有整数解，而 故命题正确 当时，原方程有且只有一个非负整数解 而 因为 所以 原方程有整数解 其中，由于，故中一正一负，可设 原方程的一般解是： 要求，仅当 是整数时，才能取 ，否则 故这个不等式的整数解个数 是 ：当是整数时 因而 当 不是整数时 因而 所以 证明2：二元一次不定方程ax + by = N的一切整数解为，tZ，于是由x 0，y 0得，但区间的长度是，故此区间内的整数个数为+ 1。：4、证明：二元一次不定方程 ，当 时有非负整数解， 则不然。证明：先证后一点，当 时，原方程有非负整数解 则，这是不可能的。次证，当Nab-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 = (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。解：设(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一奇一偶。反之，易验证()或()是原不定方程的解，且x 0，y 0，z 0，(x, y) = 1。3证明不等式方程的一切正整数解可以写成公式: ，其中 证明:由定理1知道原方程的解是， 且c， d为一奇一偶，其中， 且a， 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)xy(modm)、i=1，2，、，k则(modm)特别地，若（modm），i=0，1，则（modm）(ii)若ab(modm)，k（iii）若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整除证明 ：由上题(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 + 2，其中qZ，所以= (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） 设对整数，结论成立，即若两两互质，令，当分别通过模的完全剩余系时，必过模的完全剩余系，其中。现增加使 ，令，则易知，再令，当过模的完全剩余系，过模的完全剩余系时，据本节定理3，必过模的完全剩余系，即对结论成立。3、（i）证明整数中每一个整数有而且只有一种方法表示成的形状，其中；反之，中每一数都。 （ii）说明应用个特别的砝码，在天平上可以量出1到H中的任意一个斤数。证明：（i）当时，过模的绝对最小完全剩余系，也就是表示中的个整数，事实上，当时，共有个值，且两两互不相等，否则此即又的最大值是最小值是所以，结论成立。（ii）特制个砝码分别重斤，把要称的物体及取-1的砝码放在天平的右盘，取1的砝码放在左盘，则从（i）的结论知，当取适当的值时，可使之值等于你所要称的物体的斤数。4、若是K个两两互质的正整数，分别过模的完全剩余系，则通过模的完全剩余系。证明：（数学归纳法）（1）时，分别过模的完全剩余系时，共有个值，且若，且，即时结论成立；（2）设当分别过模的完全剩余系时，过模的完全剩余系。因为，由本节定理2得，亦过模的完全剩余系。当分别过模的完全剩余系时，2有个值，且据归纳假设，若； ，。所以过模的完全剩余系。3简化剩余系与欧拉函数1证明定理2：若是与互质的整数，并且两对模不同余，则是模的一个简化剩余系。证明： 两对模不同余，所以它们分别取自模的不同剩余类，又恰是个与互质的整数，即它们恰取自与模互质的全部剩余类。2若是大于1的正整数，是整数，通过的简化剩余系，则，其中表示展布在所通过的一切值上的和式。证明：由定理3知，通过的简化剩余系：，其中0且，而（）。若2，则必是偶数，又由，得，且易见，故所以左边每一项都存在另一项，使得，右边共有对，此即。特别地，当m=2时，。3（i）证明，p质数。(ii) 证明，其中展布在a的一切正整数上的和式。证明：（i）因为，所以 = =(ii)设是a的标准分解式，则， = =a4若是k个两两互质的正整数， 分别通过模的简化剩余系，则 通过模的简化剩余系，其中。证明：（数学归纳法）（1） 由定理4知k=2时，结论成立；（2） 设k-1时结论成立，即，分别过模时，过模的简化剩余系。显见，则又由定理4知，通过模的简化剩余系，注意到：所以，通过模m的简化剩余系。欧拉定理费马定理及其对循环小数的应用、如果今天是星期一，问从今天起再过天是星期几？解：若被除的非负最小剩余是，则这一天就是星期（当时是星期日），由费马定理得，又即这一天是星期五、求被除的余数。解：，据欧拉定理，易知（）又故则由（）即得由以上计算，知、证明下列事实但不许用定理推论：若是质数，是整数，则。由证明定理推论，然后再由定理推论证明定理。证明对应用数学归纳法：当时，按二项式展开即得设时，结论成立，即当时，结论成立。在的结论中，令，即得：即定理推论成立。进一步，设，则固对任一整数，若，则由上述已证性质得：存在，使故=（）依此类推可得若，则 ，定理成立。4、证明：有理数表成纯循环小数的充分与必要条件是有一正数t使得同余式成立，并且使上式成立的最小正整数t就是循环节的长度。证明：必要性，若结论成立，则由定理2知（b，10）=1，令t=则据欧拉定理得；充分性，若有正数t，满足令t为使上式成立的最小正整数，且=且。以下参照课本51页的证明可得：=即可表成循环小数，但循环节的长度就是t。第四章 同余式 1 基本概念及一次同余式例 解同余式 解：（12，45）= 同余多项式有3个解 而原同余式为 4 与也一样所以原同余式的3个解是 （、）即，1、 求下列各同余式的解 256x179 1215x5601296x1125337是素数， ，原同余式有唯一解。先解同余式256x1由辗转相除法，得上述同余式的解是原同余式的解是（1215，2755）=5，故先解 243x112 同的方法的得其解是原同余式的解是(1296，1935)=9，故原同余式有9个解。 由144x125得原同余式的解是2求联立同余式的解。解：据同余式的有关性质，为所求的解。3(i)设是正整数，证明 是同余式 的解(ii)设是质数，证明是同余式的解证明: (i) ， 有唯一解而据欧拉定理，得 ， 即 是的解(ii) 即有唯一解又 个连续整数之积必被所整除，故可令 则即即 是的解设p是素数，0 a 2）的原根是存在的，试证对模m的任一原根来说，的指标总是证明：模m的原根存在，故m=4，或 设为模m的一个原根，则 从而 若m=4，则模m有且只有一个原根3， ， 故的指标为若，为奇质数，则由知或但二者不能同时成立，否则，矛盾!若又由（*）知 （mod m），与的指数为矛盾。从而，从而 （mod m）故-1的指标为。 若，为的原根，则为奇数 类似于的讨论，我们有，从而 从而 （mod m）故-1的指标为。5、设，是模的两个原根，试证： （mod ）； （mod ）。证明：由指标的定义知： （mod m）两边对原根取指标： （mod ） 故 （mod ）由指标的定义知： （mod m）两边对原根取指标： （mod ）故 （mod ）。 （证毕）第九章数论函数1 可乘函数1设是一个可乘函数，证明也是一个可乘函数由此说明是可乘函数证明：首先我们证明：设，若跑过的全部因子，跑过的全部因子，则跑过的全部因子，事实上，因为，故，且当，时，由于，得，反之任给，由于，设，显然因此故为一个可乘函数(此为65页)若，它为可乘函数，且若，它为可乘函数，且故为可乘函数2设是一个定义在一切正态数的函数，并且是一个可乘函数，证明是可乘函数证明：反证，假设不是可乘函数，则存在一对正态数，使得，于是我们可以选择这样一对，使得最小若，则，即，又，为可乘函数，故有矛盾！若，则对所有正态数对，有 于是有： = =因为，故此与 为可乘函数矛盾！3证明：证明：首先易证，若d为的正约数，那么a的完全剩余系中与的最大公约数是d的个数为。其次，若为的所有正约数。那么也是的所有正约数，于是 最后，在的完全剩余系中住一数与的最大公约数必定是中某一个，而完全剩余系中与