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

初等数论习题解答（第三版） 1 / 77 第一章 整数的可除性 1 整除的概念 带余除法 1证明定理 3 定理 3 若12 na a a， ， ，都是 m 得倍数，12 nq q q， ， ，是任意 n 个整数，则1 1 2 2 a q a q a 是 m 得倍数 证明： 12,na a m 的倍数。 存在 n 个整数 12,np p p 使 1 1 2 2, , , p m a p m a p m 又12, , , nq 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 / 77 证： ,全为 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|a x b y a x b y 00|a x b y a x b y（ , 0 0 0 0| , |a x b y a a x b y b 00| ( , ) .a x b y a b又有 ( , )|a b a ， ( , )|a b b 00( , ) |a b a x b y故00( , )a x b y a b4若 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 / 77 11 02 2 2 2a b s a b a b t 若 0b ，则令 11,22t a b s a b ，则同样有2 ， 综上 所述 ， 存在性得证 下证唯一性 当 b 为奇数时，设11a b s t b s t 则11()t t b s s b 而1 1 1,22t t t t t b 矛盾 故 11,s s t t 当 b 为偶数时， ,例如下：此时2113 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 b q r br q r rr q r r r r b ( , ) na b r d | 1a 1r ， d | 1 2 2b r q r， , d | 21 ( , )n n n nr r q r a b , 即 d 是 ( , )因数。 初等数论习题解答（第三版） 4 / 77 反过来 ( , )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 b s 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 ( 7 6 5 0 1 , 9 7 1 9 )( 9 7 1 9 , 7 6 5 0 1 9 7 1 9 7 )( 8 4 6 8 , 9 7 1 9 8 4 6 8 )( 1 2 5 1 , 8 4 6 8 1 2 5 1 6 )( 3 , 1 )1 4证明本节（ 1）式中的 初等数论习题解答（第三版） 5 / 77 证：由 习题 4 知在（ 1）式中有 12 11 210 2 2 2 2r ，而1 , 22 b ， 2l o gl o g l o g 2 ，即 3 整除的进一步性质及最小公倍数 1证明两整数 a， b 互质的充分与必要条件是：存在两个整数 s， t 满足条件 1ax 证明 必要性。若 ( , ) 1，则由推论 存在两个整数 s， t 满足： ( , )a s b t 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 n1| | ( 1 , 2 , , )ia m i n又设1 2 2 | | , | | , , | | na a a m则21|之若2| |2|2|而12即12 , , , na a a=1 2 2 | |, | |, , | |na a 11 1 0x a x a x a （ 1） 是一个整数系数多项式且0a，（ 1）的根只能是以0由此推出 2 不是有理数 证：设（ 1）的任一有理根为 ( , ) 1, 1p q q。则 初等数论习题解答（第三版） 6 / 77 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 整除上式的右端，所以 | a p，又 ( , ) 1, 1p q q， 所以 ( , ) 1 , |p q a； 又由（ 2）有 111 1 0n n n p a p q a p q a q 因为 p 整除上式的右端，所以0| nP a q， ( , ) 1, 1p q q，所以 ( , ) 1 , |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 / 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，所以 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 32 3 11A ； 同理有 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 / 77 其中 m , )i i i ， m , )i i i ， 1, 2, , 证： m , )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 ， m a x , i i i 推广 设 11 1 1 21 1 2 p p p , 22 1 2 22 1 2 p p p , 1212, n n n p p p (其中, 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 i n , 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 / 77 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 1 0 3 1 0 1 4 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 / 77 所以 n m n n m n , 所以 n m n n m 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 / 77 又当 0 , 1 ) , ( ) 0 0 0 , , ( ) 0f R f 时 ， 即 101 。 评注 ： 证一 充分体现了 常规 方法的特点，而 证二 则表现了较高的技巧。 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 / 77 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 / 77 未找到引用源。 内的整点数，证明： 证明： (略 ) 5. 设 错误 !未找到引用源。 任一正整数，且 错误 !未找到引用源。 ， p 是质数， 错误 !未找到引用 源。 ，证明：在 错误 !未找到引用源。 的标准分解式中，质因数 p 的指数是 其中 错误 !未找到引用源。 . 证明：在 错误 !未找到引用源。 的标准分解式中，质因数 p 的指数有限，即 错误 !未找到引用源。 ， 错误 !未找到引用源。 所以 而 第二章 不定方程 2 1 习题 1、解下列不定方程 )1 5 2 5 1 0 0a x y 6 303 603 06) 初等数论习题解答（第三版） 14 / 77 解： )a 原方程等价于： 3 5 20 显然它有一个整数解 001 0 , 2 ， 故一般解为 1 0 5 ( 0 , 1 , 2 , )23xt )b 原方程等价于： 1 7 2 0 3 5 显然它有一个整数解 007 3 5 , 6 3 5 故一般解为 7 3 5 2 0( 0 , 1 , 2 , )6 3 5 1 7xt 2、把 100 分成两份，使一份可被 7 整除，一份可被 11整除。 解：依题意 即求 7 1 1 1 0 0 的正整数解，解得 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整数时，才能取 0yt a，否则 0yt a 初等数论习题解答（第三版） 15 / 77 故这个不等式的整数解个数 T 是 ： 当是整数时 0 0 0 011x y x yT b a b a 因而 00 1b b a a b 当 00 0 0 0 1x y x yT b 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 a b a b 则不然。 证明：先证后一点，当 N ab a b 时，原方程有非负整数解 00, ).d m m0 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 b ty y a t t 要求 0， 00 会证明存在满足这个不等式的整数0取使00 ( 0 )x b t r r b 于是对于这个0 初等数论习题解答（第三版） 16 / 77 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 / 77 ,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 a 从而 ， 为证得 , , 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 / 77 不定方程的解，且 x 0， y 0， z 0， (x, y) = 1。 3 证明不等式方程 22 4 , , 1 , 0 , 0 , /x y x y z z 的一切正整数解 可以写成公式 : 224 ( ) ,x a b 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 a b 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 = 满足 (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 / 77 1、 证明（ i）若1 k 1 k(yi( i=1， 2，、， k 则11111 , ,1 1 , , 1, 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