《初等数论(闵嗣鹤)》课后习题解答2012修改版

初等数论习题解答（修改版） （茂名学院 1 / 63 第一章 整数的可除性 1 整除的概念 带余除法 1证明定理 3 定理 3 若 12 na a a， ， ， 都是 12 nq q q， ， ， 是任意 n 个整数，则1 1 2 2 a q a q a 是 m 得倍数 证明： 12,na a a 都是 m 的倍数。 存在 n 个整数 12,np p p 使 1 1 2 2, , , p m a p m a p m 又 12, , , nq q q 是任意 n 个整数 1 1 2 2 a q a q a 1 1 2 2 p m q p m q p m 1 1 2 2()q q p q p m 即 1 1 2 2 a q a q a 是 m 的整数 2证明 3 | ( 1)(2 1)n n n 证明 ( 1 ) ( 2 1 ) ( 1 ) ( 2 1 )n n n n n n n ( 1 ) ( 2 ) ( 1 ) ( 1 )n n n n n n 又 ( 1)( 2)n n n， ( 1) ( 2)n n n是连续的三个整数 故 3 | ( 1 ) ( 2 ) , 3 | ( 1 ) ( 1 )n n n n n n 3 | ( 1 ) ( 2 ) ( 1 ) ( 1 )n n n n n n 从而可知 3 | ( 1)(2 1)n n n 3若 00ax 是形如 ax （ x， y 是任意整数， a， b 是两不全为零的整数）的数中最小整数，则 00( ) | ( )a x b y a x b y 初等数论习题解答（修改版） （茂名学院 2 / 63 证： ,全为 0 在整数集合 |,S a x b y x y Z 中存在正整数，因而有形如 ax 的最小整数00ax ,x y Z，由带余除法有 0 0 0 0( ) , 0a x b y a x b y q r r a x b y 则 00( ) ( )r x x q a y y q b S ，由 00ax 是 S 中的最小整数知 0r 00|ax by ax 00|ax by ax （ , 0 0 0 0| , |a x b y a a x b y b 00| ( , )by a b 又有 ( , )|ab a ， ( , )|ab b 00( , ) |a b ax 故 00( , )ax by a b 4若 a， b 是任意二整数，且 0b ，证明：存在两个整数 s， t 使得 |, | | 2ba b s t t 成立，并且当 b 是奇数时， s， t 是唯一存在的当 b 是偶数时结果如何？ 证：作序列 33, , , , 0 , , , ,2 2 2 2b b b 则 a 必在此序列的某两项之间 即存在一个整数 q ，使 122a b 成立 ()i 当 q 为偶数时，若 则令 ,22t a b s a b ，则有 0 2 2 2 2bq q qa b s t a b a b b t 若 0b 则令 ,22t a b s a b ，则同样有 2 () q 为奇数时，若 0b 则令 11,22t a b s a b ，则有 初等数论习题解答（修改版） （茂名学院 3 / 63 11 02 2 2 2a b s a b a b t 若 0b ，则令 11,22t a b s a b ，则同样有 2综上 所述 ， 存在性得证 下证唯一性 当 b 为奇数时，设 11a bs t bs t 则 11()t t b s s b 而1 1 1,22t t t t t b 矛盾 故 11,s s t t 当 b 为偶数时， ,例如下：此时 2b 为整数 113 1 2 ( ) , ,2 2 2 2 2b b b b bb b t t 2 最大公因数与辗转相除法 1证明推论 论 a， b 的公因数与（ a， b）的因数相同 证：设 d 是 a， b 的任一公因数， d |a， d |b 由带余除法 111 2 2 21111 1 1,0nn n n n na bq r br q r rr q r r r r b ( , ) r d | 1a 1r ， d | 1 2 2b rq r， , d | 21 ( , )n n n nr r q r a b , 即 d 是 (, )因数。 初等数论习题解答（修改版） （茂名学院 4 / 63 反过来 (, )a 且 (, )b ，若 |( , ),d a b 则 | , |d a d b ，所以 (, )因数都是 ,而 , )因数相同。 2 证明： 见本书 3 题证明。 3应用 1 习题 4 证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（ 76501， 9719） 解：有 1 习题 4 知： , , 0 , , ,a b Z b s t Z 使 ,| | 2ba bs t t 。， 11, ，使 1 1 1 2|, | | , ,22s t t t 如此类推知： 21, , ;n n n n n ns t t t s t 1 1 1 1 1, , ;n n n n n ns t t t s t 且 1221| | | | | | | | 2 2 2 2 而 b 是一个有限数， , 使 1 0 1 1 2 1( , ) ( , ) ( , ) ( , ) ( , ) ( , 0 )n n n na b b t t t t t t t t t ，存在其求法为：1( , ) ( , ) ( , ( ) )a b b a b s a b s b a b s s ( 76501 , 9719)( 9719 , 76501 9719 7 )( 8468 , 9719 8468 )(1251 , 8468 1251 6)( 3 ,1 )1 4证明本节（ 1）式中的 初等数论习题解答（修改版） （茂名学院 5 / 63 证：由 习题 4 知在（ 1）式中有 12 11 210 2 2 2 2r ，而 1 1 , 22 b ， 2 lo g lo g 2 ，即 3 整除的进一步性质及最小公倍数 1证明两整数 a， b 互质的充分与必要条件是：存在两个整数 s， t 满足条件 1ax 证明 必要性。若 ( , ) 1，则由推论 存在两个整数 s， t 满足： ( , )as bt a b ，1as 充分性。若存在整数 s， t 使 as+，则 a， b 不全为 0。 又因为 ( , ) | ,( , ) |a b a a b b，所以 ( , | )a b as 即 ( , )|1 又 ( , ) 0， ( , ) 1 2证明定理 3 定理 3 1 2 1 2, , | |, | | , | |a a a a a 证：设 1 2 1 , , , na a a m，则 1| ( 1, 2, , )ia m i n 1| | ( 1, 2, , )ia m i n 又设 1 2 2| |, | |, , | |na a a m 则 21|之若 2| | 2|12| 从而 12，即 12 , , , na a a = 1 2 2| |,| |, ,| |na a a 3设 11 1 0x a x a x a （ 1） 是一个整数系数多项式且 0a ， 不是零，则（ 1）的根只能是以 0a 的因数作分子以 分母的既约分数，并由此推出 2 不是有理数 证：设（ 1）的任一有理根为 ( , ) 1, 1p q q。则 初等数论习题解答（修改版） （茂名学院 6 / 63 11 1 0( ) ( ) 0p pa a a aq q q 111 1 0 0n n n p a p q a p q a q （ 2） 由 111 1 0( 2 ) n n n p a p q a p q a q ， 所以 q 整除上式的右端，所以 | 又 ( , ) 1, 1p q q， 所以 ( , ) 1, |n nq p q a ； 又由（ 2）有 111 1 0n n n p a p q a p q a q 因为 p 整除上式的右端，所以 0| ， ( , ) 1, 1p q q，所以 ( , ) 1, |n nq p p a 故（ 1）的有理根为 0| , | np a q a 。 假设 2 为有理数， 22 , 2 0 ，次方程为整系数方程，则由上述结论，可知其有有理根只能是 1, 2，这与 2 为其有理根矛盾。故 2 为无理数。 另证，设 2 为有理数 2 = , , ) 1, 1p q q，则2 2 2 2 2 2 2 222 , 2 , ( , ) ( 2 , ) 1p q p p q q p 但由 ( , ) 1, 1p q q知 22( , ) 1，矛盾，故 2 不是有理数。 4 质数 算术基本定理 1试造不超过 100 的质数表 解：用 选法 （ 1）算出 100 10 a （ 2） 10 内的质数为： 2， 3， 5， 7 初等数论习题解答（修改版） （茂名学院 7 / 63 （ 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，所以 38 | , 8 2 7 9 8 8 4 8 8 1 0 3 4 9 8 5 6 2A A B ， 又 8|856，所以 8|B， 38 1 2 9 3 7 3 2 2 ， 又 4|32，所以 4|C， 24 3 2 3 4 3 3 2 又 9|（ 3+2+3+4+3+3），所以 9|D， 29 3 5 9 3 7 3 ， 又 9|（ 3+5+9+3+7），所以 9|E， 9 3993E 又 33 9 9 3 3 1 3 3 1 3 1 1 所以 8 5 32311A ； 同理有 3 3 4 3 281057226635000 2 3 5 7 11 17 23 37 。 3证明推论 推广到 n 个正整数的情形 推论 设 a， b 是任意两个正整数，且 12 p p p ， 0i ， 1,2, ,， 12 p p p ， 0i ， 1,2, ,， 则 12( , ) b p p p ， 12 , b p p p ， 初等数论习题解答（修改版） （茂名学院 8 / 63 其中 , )i i i ， , )i i i ， 1,2, , 证： , )i i i ， 0 , 0i i i i | , |i i i ii i i ip p p p ( 1,2 ) 11，11. 1212 | ( , )p p a b ，又显然 1212( , ) | b p p p 1212 ( , )p p a b ，同理可得 1212 , p p a b ， , i i i 推广 设 111 121 1 2 p p p , 221 222 1 2 p p p , 1212, n n n p p p (其中 质数 1,2, , , ij k a 为任意 n 个正整数 1, 2, , , 0)， 则 121 2 1 2 1( , , , ) , m i n , 1 , 2 , ,i i i kk n i j i p p a a a j k 121 2 1 2 1 , , , , m a x , 1 , 2 , ,i i i kk n i j i p p a a a j k 4应用推论 明 3 的定理 4（ 证： 设 1 2 1 11 2 1 2p p p b p p p ， 其中 , i， i（ 1 i k）都是非负整数，有11111212( , ) m , 1 , m a x , 1i i ik i i ia b p p p i ka b p p p i k ， ， ， ， 。 由此知 (a, b)a, b = m i n , m a x , 1 1 1i i i i i i i ik k ki i ii i ip p p =从而有 , ( , ) 若 是质数（ n1），则 n 是 2 的方幂 证：（反证法）设 2(kn l l 为奇数）， 则 2 2 2 2 ( 1 ) 2 ( 2 )2 1 2 1 ( 2 ) 1 ( 2 1 ) 2 2 1 k k k k kn l l l l 初等数论习题解答（修改版） （茂名学院 9 / 63 221 2 1 ( 2 ) 1 2 1kk ， 21n 为合数矛盾，故一定为的方幂 5 函数 x,x及其在数论中的一个应用 1求 30！的标准分解式 解： 30 内的素数为 2， 3， 5， 7， 11， 13， 17， 19， 23， 29 2 2 3 4 53 0 3 0 3 0 3 0 3 02 2 2 2 2 1 5 4 3 1 0 2 3 3 2343 0 3 0 3 0 3 03 3 3 3 10 3 1 0 14 5 233 0 3 0 3 0 6 1 0 75 5 5 7 23 0 3 0 4 0 477 ，11 23 0 3 0 2 0 21 1 1 1 13 23 0 3 0 2 0 21 3 1 3 ，13 23 0 3 0 2 0 21 3 1 3 17 23 0 3 0 1 0 11 7 1 7 ， 1 9 1 9 2 3 2 9 1 2 3 1 4 5 4 2 23 0! 2 3 5 7 1 1 1 3 1 7 1 9 2 3 2 9 2设 n 是任一正整数， 是实数，证明： (i) ( 11 n 证： (i)设 m I 知 1 , 初等数论习题解答（修改版） （茂名学院 10 / 63 所以 nm n nm n , 所以 nm n nm n ，所以 1 ，又在与 +之间只有唯一整数，所以 n (证法一 设 1 , 0 , 1 , 2 , , 1kk , 则 1 , k n k n n k 当 1i k n 时 , 1 1 , i k i in n n ; 当 i k n时 , 2 1 , 1i k i in n n ; 1 1 10011 1 ( ) ( 1 )n n k ni i i n n nn k 10 证法二 令 10( ) , 1011( ) 1 ( )n 1011( ) 1 ( )n ()f 是以 1n 为周期的函数。 初等数论习题解答（修改版） （茂名学院 11 / 63 又当 0 ,1 ) , ( ) 0 0 0 , , ( ) 0f R f 时 ， 即 101 ni 。 评注 ： 证一 充分体现了 常规方法的特点，而 证二 则表现了较高的技巧。 3设 ， 是任意二实数，证明： (i) 或 1 ( 2 2 证明：（ i）由高斯函数 x的定义有 , , 0 1 ; 0 1r s r s 。则 , 1r s r s 当 0 , 时 当 0 , 1 时 故 1 或 （ , , 0 , 1x y x y ， 则有 0 2 下面分两个区间讨论： 若 01 ，则 0，所以 ，所以 2 2 2 2 2 2 2 2 2 ( ) 2 2 若 12 ，则 1，所以 1 。 所以 初等数论习题解答（修改版） （茂名学院 12 / 63 1 2 2 2 2 2 2 2 2 2( )2 2 2( 1 ) 2 2( )2 2 1 （ 证法 2）由于 ， 对称，不妨设 2 2 2 ( ) 2 ( ) 2 2 2 2 2 2 ( ) 4. (i) 设函数 在闭区间 Q x R 上是连续的，并且非负，证明 :和式 表示平面区域 Q x R ， 0 ( )y f x 内的整点（整数坐标的点）的个数 . (设 p， q 是两个互质的单正整数，证明： (设 ， T 是区域 内的整点数，证明： (设 ， T 是区域 ， ， 内的整点数，证明： 初等数论习题解答（修改版） （茂名学院 13 / 63 证明： (略 ) 5. 设 任一正整数，且 ， p 是质数， ，证明：在 的标准分解式中，质因数 p 的指数是 其中 . 证明：在 的标准分解式中，质因数 p 的指数有限，即 ， 所以 而 第二章 不定方程 2 1 习题 1、解下列不定方程 )15 25 100a x y 630360306) 初等数论习题解答（修改版） （茂名学院 14 / 63 解： )a 原方程等价于： 3 5 20 显然它有一个整数解 0010, 2 ， 故一般解为 1 0 5 ( 0 , 1 , 2 , )23xt )b 原方程等价于： 17 20 35 显然它有一个整数解 007 3 5 , 6 3 5 故一般解为 7 3 5 2 0( 0 , 1 , 2 , )6 3 5 1 7xt 2、把 100 分成两份，使一份可被 7 整除，一份可被 11整除。 解：依题意 即求 7 11 100 的正整数解，解得 008, 4 一般解是： 8 1 1 ( 0 , 1, )47xt 但除 0t 外无其他正整数解，故有且只有 100 56 44 3、证明：二元一次不定方程 , 0 , 0 , ( , ) 1a x b y N a b a b 的非负整数解为 或 1证明：当 0N 时，原方程没有整数解，而 10故命题正确 当 0N 时，原方程有且只有一个非负整数解 0,0 而 011因为 ,1 所以 原方程有整数解 10 0 0 1 1 0 2 1, , ( 1 ) , , , ( 1 ) , ,y y q q N x q q N 其中 1 2 3, , , , na q q q ，由于 0，故 00,设 0, 0 原方程的一般解是： 000 , 1,x x b t ty y a t 要求 00000 , 0 b t y a t ， 仅当 0是整数时，才能取 0，否则 0初等数论习题解答（修改版） （茂名学院 15 / 63 故这个不等式的整数解个数 T 是 ： 当是整数时 0 0 0 011x y x a b a 因而 00 1b b a a b 当 0是整数时 0 0 0 0 1x y x a b a 因而 0000 1 所以 ()m 证明 2： 二元一次不定方程 N 的一切整数解为 00x x y ， tZ，于是由 x 0， y 0 得 00 ，但区间 00,的长度是 故此区间内的整数个数为 1。 ： 4、证明：二元一次不定方程 , ( , ) 1 , 1 , 1a x b y N a b a b ，当 N ab a b 时有非负整数解， N ab a b 则不然。 证明：先证后一点，当 N ab a b 时，原方程有非负整数解 00,则 12( , ).d m m 0 0 0 01 , 1 1 , 1 , 1 , 1b x a y x b k y a h k h ,2a b k h a b k h ，这是不可能的。 次证，当 N (a， b)=1，故原方程有整数解（ ， 一般解是 00 ( 0, 1, )x x y at t 要求 x 0 0， y 0 0 00 会证明存在满足这个不等式的整数 0可取使00 (0 )x b t r r b 于是对于这个 0t 有： 初等数论习题解答（修改版） （茂名学院 16 / 63 00 11 b t r b t b 而0 0 0 0 0 000 0 01 1 1( 1 ) ( ) ( ) ( ) 10ay a t y x b b y a x a b a N a b a a b a b a b ab b b a t 这就证明了当 N ab a b 时，原方程有非负整数解 1 证明定理 2 推论。 推论 单位圆周上座标都是有理数的点（称为有理点），可以写成 2 2 2 22 2 2 2 2 2 2 222,( ) ( )a b a b a b a ba b a b a b a b 或的形式，其中 a 与 b 是不全为零的整数。 证明： 设有理数 ， （ m 0）满足方程 x 2 = 1，即 l 2 n 2 = m 2，于是得 l = 2n = (a 2 b 2)d， m = (a 2 b 2 )d 或 l = (a 2 b 2)d， m = 2m = (a 2 b 2)d，由此得 (x, y) = 2 2 2 22 2 2 2 2 2 2 222,( ) ( )a b a b a b a ba b a b a b a b 或。反之，代入方程 x 2 y 2 = 1 即知这样的点在单位圆周上。 2求出不定方程 2 2 23 , ( , ) 1 , 0 , 0 , 0x y z x y x y z 的一切正整数解的公式。 解：设不定方程 2 2 23x y z,( , ) 1有解则 (1) 3/ 3/z+x 因为 2 2 23 ( ) ( )y z x z x z x 3 / ( ) ( ) 3 /z x z x z x 或 3/z+x 2 2 22 23 333 / 3 /z x z xz x z xz x z xy y yx z 或 者得 或以下不妨设 3/ 初等数论习题解答（修改版） （茂名学院 17 / 63 ,1， 设 2 22( x , z ) d , d / x , d / z d / 3 ,y 则 22 2, 3 / , 9 / , 9 / 9 / 3 3 /dy yx z 若 3/ ,与 ,1矛盾 ! 这样 2223 , 1 / / / 3d d d 而 / / , 1d x d x y d , 1 2z x z x 或， , / ( ) ( ) 2t z x z x t z x z x x 设 ， / ( ) ( ) 2 / 2 . 2 2t z x z x z t x z 即 12或 若 , 1 , , 1 ,3x z x z x 则 223 3x z x z 从 而 由引理可设 2,3 2,z x y 从而 ， 为证得 , , 1, 必须有 a ， b 均为奇数 ， 且 223 若 , 2 , 1 , 12 2 6 2z x z x z x z xz x z x 223 2 6 2y z x z xz x z 从 而 设 2 2 2 2 2 2, , , 3 , 2 , 36 2 2z x z x y a b x y a b za b a b a b 即， 其中 , 且有 ,1 4 解不定方程： x 2 3y 2 = z 2， x 0， y 0， z 0， (x, y ) = 1。 解： 设 (z x, z x) = d，易知 d = 1 或 2。由 (z x)(z x) = 3y 2 得 z x = 3z x = y = z x = z x = 3y = a 0， b 0， (a, b ) = 1。 ( ) 当 d = 1： 2 2 2 2| 3 | 322b a b ax y a b z ， ， a 0， b 0， (a, b ) = 1， 3 | b， a, b 同为奇数； ( ) 当 d = 2： x = |b 2 3a 2 |， y = 2z = b 2 3a 2，a 0， b 0， (a, b ) = 1， 3 | b， a, b 一奇一偶。反之，易验证 ( )或 ( )是原初等数论习题解答（修改版） （茂名学院 18 / 63 不定方程的解，且 x 0， y 0， z 0， (x, y) = 1。 3 证明不等式方程 22 4 , , 1 , 0 , 0 , /x y x y z z 的一切正整数解 可以写成公式 : 224 ( ),x ab y 4 4 2 26a b a b ， 22z 其中 0 , 0 , , 1 , ,a b a b a b 一 单 一 双 证明 :由定理 1 知道原方程的解是 2 2 2 22 , , ,x c d y zc d c d 0, , 1c d c d ， 且 c， d 为一奇一偶 ， 其中 ， 222 , , 0 , , 1c a b d a b a ， 且 a， b 为一奇一偶 所以 224 ( ),x ab y 4 4 2 26a b a b ， 22z 是原方程的正整数解 22( 0 , 0 , 0 , , 1 , 2 / ,x y z x y x 且 是 奇 数， 原方程正整数的解有 : 000,， ， 20,， ， 2,0, 2 2 4 4 2 2 2 24 ( ) , ( 6 ) , ( )ab a b a b a b a b ， 4 4 2 2 2 2 2 2( 6 ) , 4 ( ) , ( ) ,b a b a b a b 6 求方程 x 2 y 2 = z 4 的满足 (x, y ) = 1， 2x 的正整数解。 解： 设 x， y， z 是 x 2 y 2 = z 4 的满足 (x, y) = 1， 2x 的正整数解，则 x = 2ab，y = a 2 b 2， z 2 = a 2 b 2， a b 0， (a, b) = 1， a, b 一奇一偶， 再由 z 2 = a 2 b 2 得 a = 2b = u 2 v 2， z = u 2 v 2 或 a = u 2 v 2， b = 2 z = u 2 v 2， u v 0， (u, v) = 1， u, v 一奇一偶，于是得 x = 4uv(u 2 v 2 )， y = |u 4 v 4 6u 2 v 2 |，z = u 2 v 2， u v 0， (u, v) = 1， u, v 一奇一偶。反之，易验证它是原不定方程的整数解，且 x 0， y 0， z 0， (x, y) = 1， 2x。 其中正负号可任意选取 第三章 同余 1 同余的概念及其基本性质 初等数论习题解答（修改版） （茂名学院 19 / 63 1、 证明（ i）若1 k 1 k( i=1， 2，、， k 则11111, ,1 1 , , 1,k kx x y y (特别地，若 （ ， i=0， 1， ,n 则 111 0 1 0n n n nn n n na x a x a b x b x b （ ( a b( k 0 , (m o d ),a k b k m k （ a b( d 是 a， b 及 m 的任一正公因数，则 (,a b mb d d ( a b( , 0.d m d 则 a b( 证明 ：（ i）据性质戊，由 ( m o d ) , 1 , 2 , , y m i k 得 ( m o d ) , 1 , 2 , , ,y m i k 进一步，则 111 1 ( m o d )x B y y m 最后据性质丁，可得： 11111, ,1 1 , , 1,k kx x y y （ (据定理 1， a b(,m a b 0 , ( )k m k k a b k a k b 又据定理 1，即得 (kb （ 定理 1， a b(,m a b即 ms(sz) , , , 0 , a b md a b m d ， 即 ,a b m sd d d 仍据定理 1，立得 (,a b mb d d (据定理 1， a b(, ( ),a a m s s z 初等数论习题解答（修改版） （茂名学院 20 / 63 又 , , ,d m m d t t z 故 ( ), ,a b m s d s t s t z (.a b d 2、设正整数 1101 0 1 0 , 0 1 0n ia a a a a 试证 11 整除的充分且必要条件是 11 整除1 ( 1) a 证明 ： 10 1(m 1), 由上题 (i)的特殊情形立得 1101 0