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

初等数论习题解答（第三版）第一章 整数的可除性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) 设函数在闭区间上是连续的，并且非负，证明:和式表示平面区域，内的整点（整数坐标的点）的个数.(ii) 设p，q是两个互质的单正整数，证明：(iii) 设，T 是区域 内的整点数，证明：(iv) 设，T 是区域， 内的整点数，证明：证明：(略) 5. 设任一正整数，且，p 是质数，证明：在的标准分解式中，质因数p的指数是其中.证明：在的标准分解式中，质因数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 p，证明：(mod p)。是同余方程ax b (mod p)的解。解：首先易知是整数，又由(a, p) = 1知方程ax b (mod p)解唯一，故只须将(mod p)代入ax b (mod p)验证它是同余方程的解即可。4设是正整数，是实数，证明同余式有解证明: 因 故同余式 必有解，(i) 若 ，则结论成立;(ii) 若，令，则又若 则由 ，结论成立若 令 则 又若 则由即 故 结论成立。若又令 则 重复上述讨论：即若 则结论成立， 若又令 例解同余方程组解：互质，故原方程组对模有唯一解即根据孙子定理方程组的解是注意到 故有限步后，必有 其中即结论成立。孙子定理试解下列各题：（i） 十一数余三，七二数余二，十三数余一，问本数。（ii） 二数余一，五数余二，七数余三，九数余四，问本数。 （杨辉：续古摘奇算法（1275）。解：（i）依题意得则据孙子定理，上述方程组有唯一解由故原方程组的解是(ii)依题意得2、（i）设 是三个正整数，证明： （ii）设 证明：同余式组 （1）有解的充分与必要条件是在有解的情况下，适合（1）的一切整数可由下式求出：其中是适合的一个整数。应用证明同余式组 有解的充分与必要条件是，并且有解的情况下，适合的一切整数可由下式求出：其中是适合的一个整数。证明： 即 设有解，即故此得，必要性成立；反之，设即则由1定理，知方程必有解，设其解为，即令则易见：且即有解，充分性得证。进一步，若有解，则即是的公倍数，当然也是的倍数，故若是的一个解，则的任一解必满足。若同余式组有解，则 也有解。从而由知必有，必要性成立。下证充分性。首先，推，用归纳法易证：又由知时，充分性也成立；现设同余式组 有解，即。设；又由条件知，而，从而，所以，即，又由，则同余式组，必有解 （）显然，即（）就是同余式组的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。3 高次同余式的解数及解法1、 解同余式。解：原同余式等价于 据孙子定理，可得故原同余式共有6个解是：2、 解同余式解： 故原同余式等价于1） 先解即 得再解即 设 而由孙子定理设即原四条式有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 代入，知后者有解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的倍数，故原方程没有三个解； () 因为这是对模5的同余方程，故原方程不可能有六个解。定理5 若p是素数，np - 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、 设， ， 证明同余式 有解的充分必要条件是，并且在有解的情况下就有个解。证明：设则但则由 可得。它有个解。 令则无多于个解，而 恰有个解，必有个解。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)的任意一个解，则一次同余方程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、 在同余式中，若，试求出它的一切解来。解：若，则，上同余式即为从而，即有。易见，当为偶数时，则，上同余式有解：，共有个解当为奇数时，上同余式有解：，共有个解。2、证明：同余式 有解的充分必要条件是 有解，并且前一同余式的一切解可由后一同余式的解导出。证明：因，故用乘后再配方，即得仍记为，即有由以上讨论即知若为的解，则为的解，必要性得证。反之，若有一解，即有：由于，故有解即有：即有：由，即有：即为的解，充分性得证。由充分性的讨论即知的解可由的解导出。2 单质数的平方剩余与平方非剩余1、 求出模的平方剩余与平方非剩余。解：，由书中定理2知，模的简化剩余系中个平方剩余分别与序列例2试判断下述同余方程是否是有解。 （1） （2） （3）中之一数同余，而 故模37的平方剩余为： 1，3，4，7，9，10，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为模的简化剩余系中的平方剩余。若模的简化剩余系中均为平方剩余，考虑模的绝对最小简化剩余系：它们的平方为模下的个数： 由假设模的简化剩余系中任一个数与上个数同余，而模的简化剩余系中有个数，故必有两个互相同余，矛盾。从而必有平方非剩余存在。若为平方剩余，则故从而也为平方剩余。若为平方剩余，为平方非剩余，则故从而为平方非剩余。设为模的简化剩余系中的平方剩余；为模的简化剩余系中的平方非剩余。由知，为平方非剩余，显然互不同余。故反之，由为平方剩余知故，得证。3证明：同余式，的解是 ，其中 证明：若有解，则有解， 设其解是：，即有： ，令而 ， 为整数由此两式即得： 两式相乘得： 取使得： 则 故其解为 4证明同余式 的解是 证明：首先我们证明对任意： 有下式： 因为 ，于是 因此由威尔生定理得： 其次由，可令 ，代入上式即有 故原同余式的解为 3 勒让得符号1用本节方法判断下列同余式是否有解 其中503，563，769，1013都是质数 解：，有解。，有解。 ，有解。2、求出以为平方剩余的质数的一般表达式；以为平方非剩余的质数的一般表达式。解：为模平方剩余时，必有，必有，故，必有，故为模平方非剩余时，必有，必有，故，必有，故3、设是正整数，及都是质数，说明由此证明：。证明：当时，由本节定理1的推论知为平方剩余，应用欧拉判别条件即有由，即得出而都是形如的素数，并且，所以。4 前节定理的证明1、 求以为平方剩余的质数的一般表达式，什么质数以为平方非剩余？解：由互反律 因此当它们同为或同时为时，一为，一为时，显然，当为偶数，而时，当是奇数，即时，。再因为是奇质数，关于模我们有或，当时，当时，这样为平方剩余时，为下方程组的解或由孙子定理，即可知或，立即当时，为平方剩余。为平方非剩余时，为下方程组的解或由孙子定理，即可知或，立即当时，为平方非剩余。因为当为偶数，或为奇数，时，即或时，为平方剩余，类似或，为平方非剩余。2、求以为最小平方非剩余的质数的一般表达式。解：由上题知以为平方非剩余的质数满足：又由为模的最小平方非剩余，故从而（3推证）满足的素数形如，其中只有满足故或时，为它的最小平方非剩余。5 雅可比符号1、 判断3习题1所列各同余式是否有解。略2、 求出下列同余式的解数：，其中是一个质数。解：，故故，即的解数为0 ，故解数为23 在有解的情况下，应用定理1，求同余式，的解。在有解的情况下，应用 2 定理1及3定理1的推论，求同余式，的解。解：同余式有解，故 由知故即为原同余式的解。 由知，故故因此或若前式成立，那末 即 若则原同余式的解是 即 为原同余式的解。 若后式成立，那末 由3定理1的推论知，2是模p的平方剩余，即于是： 若则原同余式的解是故为原同余式的解6 合数模的情形1. 解同余式 ，解：从同余式 得令代入得出从而即有故，再令代入 得出 ， 即从而 故 所以 为所给同余式的解从而所有的解为：（），故有四解记代入，即有：解得记，代入即有：，解得：又记，代入即有，解得: 故为其一解其余三解为： 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，则，又假设故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这样的表称为指数表。这个表就是模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 = 227，由知2是模29的最小正原根。