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

初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 1 / 77 第一章第一章 整数的可除性整数的可除性 1 整除的概念带余除法 1证明定理 3 定理 3 若 12n aaa， ， ，都是m得倍数， 12n qqq， ， ，是任意 n 个整数，则 1 122nn q aq aq a是m得倍数 证明： 12 , n a aa都是m的倍数。 存在n个整数 12 , n p pp使 1122 , nn ap m ap map m 又 12 , n q qq是任意n个整数 1 122nn q aq aq a 1122nn q p mq p mq p m 1 122 () nn p qq pq p m 即 1 122nn q aq aq a是m的整数 2证明 3| (1)(21)n nn 证明 (1)(21)(1)(21)n nnn nnn (1)(2)(1) (1)n nnnn n 又(1)(2)n nn，(1) (2)nn n是连续的三个整数 故3| (1)(2), 3|(1) (1)n nnnn n 3| (1)(2)(1) (1)n nnnn n 从而可知 3| (1)(21)n nn 3若 00 axby是形如axby（x，y 是任意整数，a，b 是两不全为零的整数）的数中最小 整数，则 00 ()|()axbyaxby 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 2 / 77 证： , a b不全为0 在整数集合| ,Saxby x yZ中存在正整数，因而有形如axby的最小整数 00 axby , x yZ，由带余除法有 0000 (),0axbyaxby qrraxby 则 00 ()()rxx q ayy q bS，由 00 axby是S中的最小整数知0r 00| axbyaxby 00| axbyaxby （, x y为任意整数） 0000 | ,|axbya axbyb 00|( , ). axbya b 又有( , )|a ba ，( , )| a bb 00 ( , )|a baxby 故 00 ( , )axbya b 4若 a，b 是任意二整数，且0b ，证明：存在两个整数 s，t 使得 | ,| | 2 b abstt 成立，并且当 b 是奇数时，s，t 是唯一存在的当 b 是偶数时结果如何？ 证：作序列 33 ,0, 2222 bbbb bb则a必在此序列的某两项之间 即存在一个整数q，使 1 22 qq bab 成立 ( ) i当q为偶数时，若0.b 则令, 22 qq stabsab，则有 0 2222 bqqq abstababbt 若0b 则令, 22 qq stabsab ，则同样有 2 b t ( )ii当q为奇数时，若0b 则令 11 , 22 qq stabsab ，则有 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 3 / 77 11 0 2222 bbqq tabsababt 若 0b ，则令 11 , 22 qq stabsab ，则同样有 2 b t ， 综上所述，存在性 得证 下证唯一性 当b为奇数时，设 11 abstbst 则 11 ()ttb ssb 而 111 , 22 bb ttttttb 矛盾 故 11 ,ss tt 当b为偶数时，, s t不唯一，举例如下：此时 2 b 为整数 11 312(), 22222 bbbbb bbtt 2 最大公因数与辗转相除法最大公因数与辗转相除法 1证明推论 4.1 推论 4.1 a，b 的公因数与（a，b）的因数相同 证：设 d 是 a，b 的任一公因数， d |a， d |b 由带余除法 11 1222 11 1 111 , , , , 0 n nnnn nn nnn abqr b rqrr rqr r r q rrrrb ( , ) n a br d | 1 abq 1 r， d | 122 brqr，, d | 21 ( , ) nnnn rrqra b , 即 d 是( , )a b的因数。 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 4 / 77 反过来( , )a b|a且( , )a b|b，若|( , ),da b则| ,|da db，所以( , )a b的因数都是, a b的公因 数，从而, a b的公因数与( , )a b的因数相同。 2证明：见本书 P2，P3 第 3 题证明。 3应用1 习题 4 证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求 法及辗转相除法实际算出（76501，9719） 解：有1 习题 4 知： ,0,a bZ bs tZ使,| | 2 b abst t。 ， 11 ,s t，使 111 2 | | ,|, 22 tb bs ttt如此类推知： 21 , ,; nnnnnn s t ttst 11111 ,; nnnn nn sttt st 且 12 21 | | | 2222 nn n nn tttb t 而 b 是一个有限数，,nN 使 1 0 n t 1121 ( , )( , )( , )( , )( ,)( ,0) nnnn a bb tt tt tt ttt ，存在其求法为： 1 ( , )( ,)(,() )a bb absabs babs s (76501,9719) (9719,76501 9719 7) (8468,97198468) (1251,8468 1251 6) (3,1) 1 4证明本节（1）式中的 log log2 b n 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 5 / 77 证：由 P31 习题 4 知在（1）式中有 121 1 21 0 2222 nn nn nn rrrb rr ，而 1n r 1,2 2 n n b b ， 2 log log log2 b nb，即 log log2 b n 3 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数 1证明两整数 a，b 互质的充分与必要条件是：存在两个整数 s，t 满足条件1axbt 证明 必要性。若( , )1a b ，则由推论 1.1 知存在两个整数 s，t 满足：( , )asbta b， 1asbt 充分性。若存在整数 s，t 使 as+bt=1，则 a，b 不全为 0。 又因为( , )| ,( , )|a ba a bb，所以( , |)a b asbt 即( , )|1a b。 又( , )0a b ，( , )1a b 2证明定理 3 定理 3 1212 ,|,|,| nn a aaaaa 证：设 121 , n a aam，则 1 |(1,2, ) i am in 1 |(1,2, ) i am in又设 122 |,|,| n aaam 则 21 |mm。反之若 2 | i am，则 2 | i am， 12 |mm 从而 12 mm，即 12 , n a aa= 122 |,|,| n aaa 3设 1 110 nn nn a xaxa xa （1） 是一个整数系数多项式且 0 a， n a都不是零，则（1）的根只能是以 0 a的因数作分子以 n a为 分母的既约分数，并由此推出2不是有理数 证：设（1）的任一有理根为 p q ，( , )1,1p qq。则 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 6 / 77 1 110 ()()0 nn nn ppp aaaa qqq 11 110 0 nnnn nn a papqa pqa q （2） 由 11 110 (2) nnnn nn a papqa pqa q ， 所以 q 整除上式的右端，所以| n n q a p，又( , )1,1p qq， 所以( ,)1,| n n q pq a ； 又由（2）有 11 110 nnnn nn a papqa pqa q 因为 p 整除上式的右端，所以 0 | n P a q ，( , )1,1p qq，所以(, )1, | n n qpp a 故（1）的有理根为 p q ，且 0 |,| n p a q a。 假设2为有理数， 2 2,20 xx，次方程为整系数方程，则由上述结论，可知其 有有理根只能是 1, 2，这与2为其有理根矛盾。故2为无理数。 另证，设2为有理数2=, p q ( , )1,1p qq，则 2 2222222 2 2,2,(,)(2,)1 p qppqqpq q 但由( , )1,1p qq知 22 (,)1pq，矛盾，故2不是有理数。 4 质数质数算术基本定理算术基本定理 1试造不超过 100 的质数表 解：用 Eratosthenes 筛选法 （1）算出10010 a （2）10 内的质数为：2，3，5，7 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 7 / 77 （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 2求 82798848 及 81057226635000 的标准式 解：因为 8|848，所以 3 8|,827988488 103498562A AB ， 又 8|856，所以 8|B， 3 8 12937322BC ， 又 4|32，所以 4|C， 2 4 3234332CD 又 9|（3+2+3+4+3+3） ，所以 9|D， 2 9 359373DE， 又 9|（3+5+9+3+7） ，所以 9|E，9 3993E 又 3 39933 13313 11 所以 853 2 3 11A ； 同理有 33432 81057226635000235711 17 23 37。 3证明推论证明推论 3.3 并推广到并推广到 n 个正整数的情形个正整数的情形 推论 3.3 设 a，b 是任意两个正整数，且 12 12 n n appp ，0 i ，1,2,ik， 12 12 n n bppp ，0 i ，1,2,ik， 则 12 12 ( , ) k k a bppp ， 12 12 , k k a bppp ， 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 8 / 77 其中min(,) iii ，min(,) iii ，1,2,ik 证：min(,) iii ，0,0 iiii |,| iiii iiii pppp (1,2)ik 11 ii kk ii ii pp ， 11 ii kk ii ii pp . 12 12 |( , ) k k p ppa b ，又显然 12 12 ( , )| k k a bp pp 12 12 ( , ) k k p ppa b ，同理可得 12 12 , k k p ppa b ，max, iii 推广 设 11112 112 k k appp , 22122 212 k k appp , 12 12 , nnnk nk appp (其中 j p为质数1,2, , i jk a为任意 n 个正整数1,2, ,0 ij in)， 则 12 1212 1 ( ,),min,1,2, iiik knijij i n pppa aajk 12 1212 1 ,max,1,2, iiik knijij i n pppa aajk 4应用推论 3.3 证明3 的定理 4（ii） 证：设 1211 1212 kk kk ap ppbp pp ， 其中 p1, p2, , pk是互不相同的素数，i，i（1 i k）都是非负整数，有 11 11 12 12 ( , )min,1 , max,1 k k kiii kiii a bp ppik a bp ppik ， ，。 由此知(a, b)a, b = min, max, 111 iiiiiiii kkk iii iii ppp =ab；从而有 , ( , ) ab a b a b 若 n 21是质数（n1） ，则 n 是 2 的方幂 证： （反证法）设2 ( k nl l为奇数） ， 则 2222 (1)2 (2) 2121(2 )1(21)221 kkkkk nllll 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 9 / 77 22 121(2 )121 kk ln ， 21 n 为合数矛盾，故一定为的方幂 5 函数函数x,x及其在数论中的一个应用及其在数论中的一个应用 1求 30！的标准分解式 解：30 内的素数为 2，3，5，7，11，13，17，19，23，29 2 2345 3030303030 22222 1543 1 023 3 234 30303030 3333 103 1 014 5 23 303030 6 107 555 7 2 3030 404 77 ， 11 2 3030 202 1111 13 2 3030 202 1313 ， 13 2 3030 202 1313 17 2 3030 101 1717 ， 19192329 1 23145422 30!235711 13 17 19 23 29 2设 n 是任一正整数，是实数，证明： (i) n n (ii) 11n n nn 证：(i)设 m.则由性质 II 知1mm, 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 10 / 77 所以 nmnnmn, 所以nmnnmn，所以 1 n mm n ，又在与+之间只有唯一整数， 所以 n m n (ii) 证法一设 1 ,0,1,2,1 kk kn nn , 则 1, knknnk 当1ikn时, 1 1, ikii nnn ; 当ikn时,2 1, 1 ikii nnn ; 111 00 11 1 () ( 1) nnkn iii n k n nn ii nnn nkk nk 1 0 n i i n n 证法二 令 1 0 ( ) n i i fn n , 1 0 11 () 1( ) n i i fnf nn 1 0 11 () 1( ) n i i fnf nn ( )f是以 1 n 为周期的函数。 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 11 / 77 又当0,1),( )000,( )0fR f时， 即 1 0 1 n i n n 。 评注：证一充分体现了 常规方法的特点，而证二则表现了较高的技巧。 3设，是任意二实数，证明： (i) 或 1 (ii) 2 2 证明： （i）由高斯函数x的定义有 , ,01;01rsrs。则 ,1rs rs 当0, rs 时 当0, 1rs 时 故 1 或 （ii）设 , ,0,1xyx y， 则有0 2xy 下面分两个区间讨论： 若01xy，则0 xy，所以 ，所以 2 2 2 2 2 2 xy 2 2 2( )xy2 2 若12xy，则1xy，所以 1。 所以 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 12 / 77 1 2 2 2 2 2 2 2 2 2( ) 2 2 2( 1) 22( ) 2 2 1 xy xy xy xx xx （ii） （证法 2）由于，对称，不妨设 2 2 2( ) 2( ) 2 2 2 2 2 2 ( ) 4. (i) 设函数在闭区间QxR上是连续的，并且非负，证明:和式 表示平面区域QxR，0( )yf x内的整点（整数坐标的点）的个数. (ii) 设 p，q 是两个互质的单正整数，证明： (iii) 设，T 是区域 内的整点数，证明： (iv) 设，T 是区域， 内的整点数，证明： 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 13 / 77 证明：(略) 5. 设任一正整数，且，p 是质数，证明：在的 标准分解式中，质因数 p 的指数是 其中. 证明：在的标准分解式中，质因数 p 的指数有限，即 ， 所以 而 第二章 不定方程 21 习题 1、解下列不定方程 )1525100axy 630360306)yxb 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 14 / 77 解：)a 原方程等价于：3520 xy 显然它有一个整数解 00 10,2xy ， 故一般解为 105 (0, 1, 2,) 23 xt t yt )b原方程等价于：172035xy 显然它有一个整数解 00 7 35,6 35xy 故一般解为 7 3520 (0, 1, 2,) 6 35 17 xt t yt 2、把 100 分成两份，使一份可被7整除，一份可被11整除。 解：依题意 即求 711100 xy 的正整数解，解得 00 8,4xy 一般解是： 8 11 (0, 1,) 47 xt t yt 但除 0t 外无其他正整数解，故有且只有 1005644 3、证明：二元一次不定方程 ,0,0,( , )1axbyN aba b 的非负整数解为 N ab 或 1 N ab 证明：当0N 时，原方程没有整数解，而 10 N ab 故命题正确 当0N 时，原方程有且只有一个非负整数解 0,0 而 0 N ab 11 N ab 因为 ,1a b 所以 原方程有整数解 1 00011021 ,( 1),( 1), nn nn xyyqqN xqqN 其中 123 , n a q q qq b ，由于0ab，故 00 ,xy中一正一负，可设0,0 xy 原方程的一般解是： 0 0 0, 1, xxbt t yyat 要求 00 00 0,0 xy xbtyatt ba ， 仅当 0 y a 是整数时，才能取 0 y t a ，否则 0 y t a 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 15 / 77 故这个不等式的整数解个数T 是 ： 当是整数时 0000 11 xyxy T baba 因而 00 1 xyNN T abbaab 当 0 y a 不是整数时 0000 1 xyxy T baba 因而 00 00 1 xy baN abxy ba 所以 ( )m 证 明证 明 2： 二 元 一 次 不 定 方 程 ax by = N 的 一 切 整 数 解 为 0 0 xxbt yyat ， tZ， 于 是 由 x 0，y 0 得 00 yx t ab ，但 区 间 00 , yx ab 的 长 度 是 N ab ，故 此 区 间 内 的 整 数 个 数 为 NN abab 或 1。 ： 4、证明：二元一次不定方程 ,( , )1,1,1axbyNa bab，当 Nabab 时有非负整数解，Nabab 则不然。 证明：先证后一点，当 Nabab时，原方程有非负整数解 00 ,xy 则 12 (,).dm m 0000 1,11,1,1,1b xa yxbk yah kh ,2ab khab kh，这是不可能的。 次证， 当Nab-a-b时， 因(a， b)=1， 故原方程有整数解 （x0， y0） ， 一般解是 0 0 (0, 1,) x xbt y yat t 要求 x 0-bt0，y0 0at 00 yx t ab 会证明存在满足这个不等式的整数 0 tt可取使 00 (0)xbtrrb于是对于这个 0 t有： 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 16 / 77 00 1 1 xb xbtrbt b 而 000000 0 000 111 (1)()()()1 0 a yatyxbbyaxabaNabaabababa bbbb y yatt a 这就证明了当Nabab时，原方程有非负整数解 1 证 明 定 理 2 推 论 。 推论推论 单位圆周上座标都是有理数的点（称为有理点） ，可以写成 2222 22222222 22 ,()() abababab abababab 或 的形式，其中 a 与 b 是不全为零的整数。 证 明 ：证 明 ： 设 有 理 数 ln xy mm ，（ m 0） 满 足 方 程 x 2 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) = 2222 22222222 22 ,() () abababab abababab 或。 反 之 ， 代 入 方 程 x2 y2 = 1 即 知 这 样 的 点 在 单 位 圆 周 上 。 2求出不定方程 222 3,( , )1,0,0,0 xyzx yxyz的一切正整数解的公式。 解：设不定方程 222 3xyz,( , )1x y 有解则 (1)3/z-x 或 3/z+x 因为 222 3()()yzxzx zx 3/ ()()3/zx zxzx或 3/z+x 222 22 3 33 3/3/ zxzx zxzx zxzx yyy xz 或者 得或 以下不妨设3/ zx 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 17 / 77 ,1x z ， 设 2 22 (x,z)d,d/x,d/zd/3, y xz 则 2 22 ,3/,9/,9/9/33/dy y xz 若 3/, x y与,1x y 矛盾! 这样 22 2 3,1/3dddy yy d 而/,1d xdx yd ,12zx zx 或， ,/()()2tzx zxtzxzxx设， /()()2/ 2 .22tzxzxztx z 即 12tt或 若,1,1, 3 zx zx zxzx 则 22 3 3 zx zxzxzx yy 从而 由引理可设 2, 3 zx a 2, zxyab b 从而 ， 为证得, x z为整数， ,1,x z 必须有 a ， b 均为奇数，且 22 3a b 若,2,1,1 2262 zx zxzx zx zx zx 2 2 3 262 yzx zx zxzx y 从而 设 222222 ,3,2,3 622 zxzxy abxyab z ababab 即， 其中, a b为一奇一偶，且有,1a 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： 2222 |3|3 22 baba xyabz ，a 0，b 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 一 奇 一 偶 。 反 之 ， 易 验 证 () 或 () 是 原 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 18 / 77 不 定 方 程 的 解 ， 且 x 0， y 0， z 0， (x, y) = 1。 3证明不等式方程 2 24, ,1,0,0, /x yxyz x y xz 的一切正整数解 可以写成公式: 22 4(),xab ab y 4422 6 aba b ， 22 z ab 其中0,0,1, ,aba ba b一单一双 证明:由定理 1 知道原方程的解是 2222 2,xcd yz cdcd 0,1cdc d， 且 c， d 为一奇一偶， 其中， 22 2,0,1cab daba b ab ， 且 a， b 为一奇一偶 所以 22 4(),xab ab y 4422 6 aba b ， 22 z ab 是原方程的正整数解 22 (0,0,0,1,2/ ,xyzx yx ab 且是奇数， 原方程正整数的解有: 0 0 0 ,， ， 2 0, a a ， 2,0, a a 22442222 4(), (6), ()aba b aba bab ， 44222222 (6), 4(), () ,ab aba ba bab 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 同余的概念及其基本性质 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 19 / 77 1、 证明（i）若 1k 1k (modm) xiyi(modm)、i=1，2， 、 、 、 ，k 则 11 11 1, 11,1 , kk kk k k k xxyy (modm) 特别地，若 ii ab（modm） ，i=0，1，,n则 11 1010 nnnn nnnn a xaxab xbxb （modm） (ii)若 ab(modm)，k0,(mod),akbkmk （iii）若 ab(modm)，d 是 a，b 及 m 的任一正公因数，则(mod), abm bdd (iv)若 ab(modm)，,0.d m d 则 ab(modd) 证明 ： （i）据性质戊，由(mod),1,2, . ii xym ik 得(mod),1,2, , ii ii xym ik 进一步，则 11 1 1 11 (mod) kk kk kk xxByym 最后据性质丁，可得： 11 11 1, 11,1 , kk kk k k k xxyy （modm） (ii) 据定理 1，ab(modm),m ab 0,()kmk k abkakb 又据定理 1，即得(mod).kakbmk （iii）据定理 1， ab(modm) ,m ab即 a-b=ms(sz) , ,0, abm d a b m ds dd ，即, abm s ddd 仍据定理 1，立得(mod), abm bdd (iv) 据定理 1， ab(modm),(),aams sz 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 20 / 77 又,d mmdt tz 故( ),abmsd ststz (mod ).abd 2、设正整数 1 10 1010,010 nn nni aaaaa 试证 11 整除的充分且必要条件是 11 整除 1 ( 1). i n i i a 证明 ：101(mod11), 由上题(i)的特殊情形立得 1 10 1010 nn nn aaaa 1 10 ( 1)( 1)(mod11) nn nn aaa 0 ( 1)(mod11), n i i i aa 0 1111( 1) i n i i aa 3找出整数能被 37，101 整除有判別条件来。 解：10001(mod37) 故正整数 1 10 10001000,01000 kk kki aaaaa 立得 0 3737. k i i aa 1001(mod101). 故设正整数 1 10 100100,0100 ss ssi abbbb ， 立得 0 101101( 1). s i i i ab 4、证明641 32 21 证明： 8 2256 mod641 初等数论习题解答（初等数论习题解答（第三第三版）版）广东石油化工学院广东石油化工学院 21 / 77 162 225665536154 mod641 322 2154237161 mod641 即641 32 21 5、若a是任一单数，则 22 1 mod2 n n a ，1n 证明： （数学归纳法）设21am （1）1n 时， 2 2 214111 mod8amm m ， 结论成立。 （2）设nk时，结论成立，即： 22 22 2110 mod22112 kk kk mmt ，tz 而 1 22222 11111 2 kkkkk aaaaa 2 22 22 2 kk tt 2243 22 kk tt 31 221 kk tt 3 0 mod2k 故1nk时，结论也成立；1n时，结论也成立。 证明：若 2 | a，n 是正整数，则 2n a 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 成立，则有 2k a 1 (mod 2k + 2) 2k a= 1 q2k + 2， 其中 qZ，所以 1 2k a = (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3)， 其中 q 是某个整数。这说明式(4)当 n = k 1 也成立。 由归纳法知式(4)对所有正整数 n 成立。 初等数论习题解答（初等数