初等数论(闵嗣鹤、严士健)习题解答及考试试题(东北师大).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 0，0，则对模的指数是( )A B C D无法确定19，均为可乘函数，则( )A为可乘函数； B为可乘函数C为可乘函数； D为可乘函数20设为茂陛乌斯函数，则有( )不成立A B C D二填空题：（每小题1分，共10分）21 3在45中的最高次n _；22 多元一次不定方程：，其中 ， ，N均为整数，有整数解的充分必要条件是_；23有理数，能表成纯循环小数的充分必要条件是_；24 设为一次同余式，的一个解，则它的所有解为_；25 威尔生（wilson）定理：_；26 勒让德符号=_；27 若，则是模的平方剩余的充分必要条件是_(欧拉判别条件)；28 在模的简化剩余系中，原根的个数是_；29 设，为模的一个原根，则模的一个原根为_；30 _。三简答题：（5分题4题20分）31命题“任意奇数的平方减1是8的倍数”对吗？说明理由。32“若，通过模的简化剩余系，则也通过模的简化剩余系”这命题是否正确？正确请证明，不正确请举反例。33求模17的简化剩余系中平方剩余与平方非剩余。34设为的标准分解式，记为的正因数的和，为的正因数的个数，则？ ？ 为什么？四计算题。（7分题4题28分）35 求不定方程6x+93y=75的一切整数解。36 解同余方程组37解同余式11(mod125)38求模13的所有原根。五、证明题：（7分/题2题=14分）39、试证： ，（x，y）=1 y是偶数的整数解可写成： 这里，并且一为奇数，一为偶数。40、设a为正整数，试证： 其中表示展布在a的一切正因数上的和式。六、应用题：（8分）41、求30！中末尾0的个数。参考答案：一单项选择：ABCDD；DACCB；DCAAD；BCBAB。 二填空题：2121；22；23；24；25！+1为素数；261；27；28；29与中的单数；3016三简答题：31答：命题正确。 而必为2的倍数。86页32正确证明见教材。33在摸的简化剩余系中与同余的数是数的平方剩余，故1，2，4，8，9，13，15，16为摸17的平方剩余，而3，5，6，7，10，11，12，14为摸17的平方非剩余。34 证明：若为可乘函数，则 分别令，它们为可乘函数，即得出。四计算题35解：因为，故原不定方程有解。 又原方程即 ，而易见方程有解 。所以原方程的一个解是所以，原方程的一切整数解是：（ ） t是整数36解：因为模5，6，7两两互质，由孙子定理得所给同余方程组关于模567210有唯一解，分别解同余方程：，得， ，因此所给同余方程组的解是：即：37解：从同余方程， ， ， 是 得即 是所给方程的一个解，于是所解为： 解毕。38解： 为其质因数 ，故g为模13的原根的主要条件是： ， 用 g=1，2，12逐一验证，得：2，6，7，11为模13的原根， 因为，故模13原根只有4个，即为所求。五、证明题：39证明：易验证所给的解为原方程的解，因y为偶数，原方程可化为： 但 而x,z=1，所以（，）=1 由书中引理，我们可假设 =， =b 显然b， (，b)=1， 于是 X=b， z=+ ，y=2 因子为奇数，所以，b一定是一为奇，一为偶，证毕40证明：假定 ，-， 为的所有正约数，那末 ，-，也是的所有正约数，于是 = 再因为在的完全剩余系中任一数的最大公约数 必定是 ，-， 中某一个数，而完全剩余系中与的最 大公约数为的数有 ，所以： = m 证毕六应用题：41解：5在30！中的最高次幂=+ =6+1+0=7 2在30！的最高次幂=+ =15+7+3+1+0=26 10=25，故 30！的末尾有7个零。初等数论模拟试题二一、单项选择题1、（C ）.A B C D 02、如果，则(D ).A B C D 3、如果，则=（C ）.A B C D 4、小于30的素数的个数（A ）.A 10 B 9 C 8 D 75、大于10且小于30的素数有（ C ）.A 4个 B 5个 C 6个 D 7个6、如果，则15（A ）.A 整除 B 不整除 C 等于 D不一定7、在整数中正素数的个数（C ）.A 有1个 B 有限多 C 无限多 D 不一定二、计算题1、 求24871与3468的最大公因数?解： 24871=34687+5953468=5955+493595=4931+102493=1024+85102=851+1785=175,所以,(24871,3468)=17.2、 求24871,3468=?解：因为 （24871,3468）=17 所以 24871,3468= =5073684 所以24871与3468的最小公倍数是5073684。3、求136,221,391=?解： 136,221,391=136,221,391 =1768,391 = =104391=40664.三、证明题1、 如果是两个整数,则存在唯一的整数对,使得,其中.证明 ：首先证明唯一性.设,是满足条件的另外整数对,即,.所以,即,.又由于,所以.如果,则等式不可能成立.因此,. 其次证明存在性.我们考虑整数的有序列,则整数应介于上面有序列的某两数之间,即存在一整数使.我们设,则有,. 2、 证明对于任意整数,数是整数. 证明： 因为=, 而且两个连续整数的乘积是2的倍数,3个连续整数的乘积是3的倍数, 并且(2,3)=1, 所以从和有,即是整数. 3、 任意一个位数与其按逆字码排列得到的数的差必是9的倍数证明： 因为 , =, 所以,-= 而上面等式右边的每一项均是9的倍数, 于是所证明的结论成立. 4、 证明相邻两个偶数的乘积是8的倍数.证明: 设相邻两个偶数分别为 所以= 而且两个连续整数的乘积是2的倍数 即是8的倍数. 初等数论模拟试题三一、单项选择题1、如果( A ),则不定方程有解.A B C D 2、不定方程（A ）.A 有解 B 无解 C 有正数解 D 有负数解 二、求解不定方程1、.解：因为（9，21）=3，所以有解； 化简得； 考虑，有， 所以原方程的特解为， 因此，所求的解是。 2、.解：因为 ,所以有解; 考虑,; 所以是特解, 即原方程的解是 3、.解：因为（107，37）=1，所以有解； 考虑，有， 所以，原方程特解为=225，=-650， 所以通解为 4.求不定方程的整数解.解 我们将它分为两个二元一次不定方程来求解25x+13y=t, t+7z=4.利用求二元一次不定方程的方法,因为25(-t)+13(2t)= t, 32+7(-4)=4,所以,上面两个方程的解分别为 , .消去t就得到所求的解,这里是任意整数.5.求不定方程的整数解.解 我们将它分为两个二元一次不定方程来求解4x-9y=t, t+5z=8.利用求二元一次不定方程的方法,因为4(-2t)-9(-t)= t, 48+5(-8)=8,所以,上面两个方程的解分别为 , .消去t就得到所求的解,这里是任意整数.初等数论模拟试题四一、选择题1、整数5874192能被( B )整除.A 3 B 3与9 C 9 D 3或92、整数637693能被(C )整除.A 3 B 5 C 7 D 93、模5的最小非负完全剩余系是( D ).A -2,-1,0,1,2 B -5,-4,-3,-2,-1 C 1,2,3,4,5 D 0,1,2,3,44、如果,是任意整数,则（A ）A B C T D 二、解同余式（组）（1）.解 因为(45,132)=321,所以同余式有3个解. 将同余式化简为等价的同余方程