2022年《初等数论》习题集及答案.docx

《2022年《初等数论》习题集及答案.docx》由会员分享，可在线阅读，更多相关《2022年《初等数论》习题集及答案.docx（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -初等数论习题集第 1 章第 1 节1. 证明定理 1；2. 证明：如 m p mn pq,就 m p mq np；3. 证明： 任意给定的连续 39 个自然数, 其中至少存在一个自然数,使得这个自然数的数字和能被 11 整除；4. 设 p 是 n 的最小素约数,n = pn1,n1 1,证明：如 p 3 n ,就 n1 是素数；5. 证明：存在无穷多个自然数 n,使得 n 不能表示为2a p（ a 0 是整数, p 为素数）的形式；第 2 节6.1.证明： 12 n4 2n3 11n2 10n,nZ；n 整2

2、. 3.设 3 a 2b 2,证明： 3 a 且 3 b；设 n,k 是正整数,证明：n k 与 n k + 4 的个位数字相同；4.证明：对于任何整数2 n,m,等式 n n 12 = m2 2 不行能成立；5. 设 a 是自然数,问a42 3a 9 是素数仍是合数？证明：对于任意给定的n 个整数,必可以从中找出如干个作和,使得这个和能被除；第 3 节6.1.证明定理 1 中的结论 ；2.证明定理 2 的推论 1, 推论 2 和推论 3；3.证明定理 4 的推论 1 和推论 3；4.5. 设 x,y Z,17 2x 3y,证明： 17 9x 5y；设 a,b,c N,c 无平方因子, a 2

3、 b 2c,证明： a b；设 n 是正整数,求C1 2 n,C3 2n,C2 2n n1的最大公约数；第 4 节1. 2.3. 4. 5.6. 证明定理 1；证明定理 3 的推论；设 a,b 是正整数,证明：aba, b = ab, ab；求正整数 a, b,使得 ab = 120,a, b = 24,a, b = 144 ；设 a,b,c 是正整数,证明：a ,a,b,c 2a a,a,b,c2,a；b b,cc ,bb ,c c设 k 是正奇数,证明：1 2 k 9 1 2k 9k；第 5 节1.说明例 1 证明中所用到的四个事实的依据； 第 1 页,共 38 页 细心整理归纳 精选学习

4、资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -2.用辗转相除法求整数x,y,使得 1387x 162y = 1387, 162 ；3.运算： 27090, 21672, 11352 ；1 的整数除所得的余数相同,4. 使用引理 1 中的记号,证明：F n + 1, F n = 1；5. 如四个整数2836,4582,5164,6522 被同一个大于且不等于零,求除数和余数各是多少？6.记 M n = 2n 1,证明：对于正整数a,b,有 M a, M b

5、 = Ma, b；第 6 节1.2.3.4. 5.6.证明定理 1 的推论 1；证明定理 1 的推论 2；写出 22345680 的标准分解式；证明：在 1, 2, , 2n 中任取 n 1 数,其中至少有一个能被另一个整除；证明：111（n 2）不是整数；2n设 a,b 是正整数,证明：存在a1,a2,b1,b2,使得a = a1a2,b = b1b2,a2, b2 = 1,并且 a, b = a2b2；第 7 节1.证明定理 1；求使 12347.被 35 k 整除的最大的k 值；= n；2.3. 设 n 是正整数, x 是实数,证明：r 1n2r12r4.设 n 是正整数,求方程x2 x

6、 2 = x x2 在1, n中的解的个数；5.证明：方程fx = x 2 x 22x 23x 24x 25x = 12345 没有实数解；6. 证明： 在 n. 的标准分解式中, 2 的指数 h = n k,其中 k 是 n 的二进制表示的位数码之和；第 8 节1. 2. 3.4.n 证明：如 2 1 是素数,就n 是 2 的乘幂；n 证明：如 2 1 是素数,就n 是素数；证明：形如6n 5 的素数有无限多个；设 d 是正整数, 6 | d,证明：在以d 为公差的等差数列中,连续三项都是素数的情形最多发生一次；5.证明：对于任意给定的正整数n,必存在连续的n 个自然数,使得它们都是合数；细

7、心整理归纳 精选学习资料 第 2 页,共 38 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -6. 证明：级数n11发散,此处使用了定理1 注 2 中的记号；pn第 2 章第 1 节1.证明定理 1 和定理 2；, fm都不能被m 整除,就 fx = 0 没有2.证明定理 4；3.证明定理 5 中的结论 ；求 8 1234 被 13 除的余数；4.5. 设 fx是整系数多项式,并且f1, f2, 整数解；6.已知 9962427,求与 ；第 2 节1. 2

8、.3.4.证明定理 1；证明：如 2p 1 是奇素数,就p.2 1p 0 mod 2 p 1；证明：如 p 是奇素数, N = 1 2 p 1,就p 1. p 1 mod N；证明 Wilson 定理的逆定理：如n 1,并且n 1. 1 mod n,就 n 是素数；5.设 m 是整数, 4 m, a1, a2, , am 与 b1, b2, , bm 是模 m 的两个完全剩余系,证明： a1b1, a2b2, , ambm 不是模 m 的完全剩余系；i n）是整数,并且6.设 m1, m2, ,mn是两两互素的正整数,i（1 i 1 mod mi,1 i n,i 0 mod mj,i j, 1

9、 i, j n；证明：当bi 通过模 mi（1 i n）的完全剩余系时,nb11b22bn通过模 m = m1m2mn的完全剩余系；第 3 节1.证明定理 1；xi 分别通过模mi 的简化剩余系 （1 in）,2.设 m1, m2, , mn是两两互素的正整数,m = m1m2mn, Mi =m ,就 m i MnxnM 1x1M 2x2通过模 m 的简化剩余系；3.设 m 1,a, m = 1,x1, x2, , xm是模 m 的简化剩余系,证明： 第 3 页,共 38 页 细心整理归纳 精选学习资料 m axi1m ；i1m2 - - - - - - - - - - - - - - - -

10、 - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -其中 x 表示 x 的小数部分；4. 设 m 与 n 是正整数,证明：mn m, n = m, n m n；5.设 a,b 是任意给定的正整数,证明：存在无穷多对正整数m 与 n,使得a m = b n；6.设 n 是正整数,证明： 1 mod 561 ,但 561 是合数；6 相像的结论？ n 1n；2 如 n 是合数,就n nn ；第 4 节证明： 1978 103 1978 3 能被 10求 313 159 被 7 除的余数；3 整除；1. 2.3.证明：对于任意的整数

11、560 a,a, 561 = 1 ,都有 a4. 设 p,q 是两个不同的素数,证明： 1 1 mod pq；pq 1p q5.将 612 1 分解成素因数之积；6.设 n N,bN,对于 bn 1 的素因数,你有甚麽与例第 5 节1.证明例 2 中的结论；p ；2.证明定理 2；3.求d|n1 ；d4.设 fn是积性函数,证明： dfd 1fd| np| np 2dfd 1fd| np|n5.求 n的 Mobius 变换；第 3 章第 1 节1.证明定理 3；n 的2.写出 789 的二进制表示和五进制表示；3.求8 的小数的循环节；214.证明：七进制表示的整数是偶数的充要条件是它的各位数

12、字之和为偶数；5.证明：既约正分数m 的 b 进制小数 0 a 1a 2a 3 nb为有限小数的充要条件是每个素因数都是b 的素因数；第 2 节细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -1.设连分数1, 2, , n, 的第 k 个渐近分数为pk,证明：qk2.pka 11100000,qk1000000,a 21100a 211000a 3100a310001ak11001ak110001a k000

13、1a k设连分数1, 2, , n, 的第 k 个渐近分数为pk,证明：qka 11a21ak1p kp k1,k 2；3.101010qkq k1求连分数 1, 2, 3, 4, 5, 的前三个渐近分数；4.求连分数 2, 3, 2, 3, 的值；5.解不定方程： 7x 9y = 4；第 3 节 101.证明定理 4；,求的误差2.求13 的连分数；3.求23的误差 10 5的有理靠近；4.求 sin18 的误差 10 5 的有理靠近；5. 已知圆周率 6 的有理靠近； = 3, 7, 15, 1, 292, 1, 1, 1, 21, 6.证明：125连分数绽开的第k 个渐近分数为F kF

14、k1 ；此处 Fn是 Fibonacci 数列；第 4 节1.将方程 3x2 2x 2 = 0 的正根写成连分数；k 个 渐 近 分 数 为pk, 证 明 ：2.求 = ,1,23之值；3.设 a 是正整数,求a21的连分数；4.设 无 理 数d = a1, a2, , an, 的 第qk 第 5 页,共 38 页 da1,a 2,an,2 a1的充要条件是pn1；pn = a1qnqn1,dqn = a1pn细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - -

15、 - - - - - -5.设无理数d = a1, a2, , an, 的第 k 个渐近分数为pk,且正整数n 使得qkpn = a1qnqn1,dqn = a1pnpn1,证明： 当 n 为偶数时, pn,qn是不定方程x22dy2 = 1 的解； 当 n 为奇数时, p2n, q2n是不定方程xdy2 = 1 的解；第 4 章第 1 节1. 2. 3.4.将17 写成三个既约分数之和,它们的分母分别是 1053,5 和 7；求方程 x1 2x2 3x 3 = 41 的全部正整数解；求解不定方程组：x 12 x23 x37；2 x15x220x311甲班有同学7 人,乙班有同学11 人,现有

16、 100 支铅笔分给这两个班,要使甲班的同学分到相同数量的铅笔,乙班同学也分到相同数量的铅笔,问应怎样分法？5. 证明：二元一次不定方程 ax by = n,a 0 ,b 0 ,a, b = 1 的非负整数解的个数为 n 或 n 1；ab ab6. 设 a 与 b 是正整数, a, b = 1 ,证明： 1, 2, , ab a b 中恰有 a 1 b 1 个整2数可以表示成 ax by（x 0,y 0）的形式；第 2 节1. 2. 3. 4. 5.6.证明定理 2 推论；设 x,y,z 是勾股数, x 是素数,证明：2z 1,2xy 1都是平方数；求整数 x,y,z, x y z,使 xy,

17、xz,yz 都是平方数；2 解不定方程： x 3y 2 = z 2, x 0,y 0, z 0,x, y = 1；证明下面的不定方程没有满意xyz 0 的整数解； x2y2z 2 = x 2y2； x2y 2z 2 = 2xyz；y 2 = z 4 的满意 x, y = 1,2 x 的正整数解；2 求方程 x第 3 节1. 2 求方程 xxy 6 = 0 的整数解； 第 6 页,共 38 页 2. 求方程组x3y3 yz018的整数解；x3 z3. x 求方程 2 3 y = 1 的正整数解；4.求方程1 x11的正整数解；yz细心整理归纳 精选学习资料 - - - - - - - - - -

18、 - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -5.设 p 是素数,求方程211的整数解；pxy6. 设 2n 1 个有理数 a1, a2, , a2n 1满意条件 P：其中任意2n 个数可以分成两组,每组 n 个数,两组数的和相等,证明：a1 = a1 = = a2n 1；第 5 章第 1 节1. 证明定理 1；2. 解同余方程： 31x 5 mod 17 ； 3215x 160 mod 235 ；3. 解同余方程组：3 x 5 y 38 mod 47 ；x y 10 mod 47 4. 设 p

19、是素数, 0 a n；第 4 节1. 解同余方程：11 8 4 3x 2x 5x 1 0 mod 7 ；20 12 7 4x 3x 2x 3x 2 0 mod 5；2. 判定3 2 2x x 3x 1 0 mod 5是否有三个解；6 5 2 x 2x 4x 3 0 mod 5 是否有六个解？k3. 设a, m = 1 ,k 与 m 是正整数,又设 x0 a mod m,证明同余方程kx amod m 的一切解 x 都可以表示成 x yx0 mod m,其中 y 满意同余方程 y k 1 mod m；n4. 设 n 是正整数, p 是素数, n, p 1 = k,证明同余方程 x 1 mod p

20、有 k 个解；5. 设 p 是素数,证明：p 1 对于一切整数 x,x 1 x 1 x 2 x p 1 mod p； p 1. 1 mod p；6. 设 p 3 是素数,证明：x 1x 2 x p 1的绽开式中除首项及常数项外,全部的系数都是 p 的倍数；第 5 节1. 2. 3.2 同余方程 x 3 mod 13 有多少个解？求出模 23 的全部的二次剩余和二次非剩余；设 p 是奇素数,证明：模p 的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余；4.设素数p 3 mod 4,n p= 1,证明 xnp1mod p是同余方程42

21、xn mod p 的解；5.设 p 是奇素数, n, p = 1,是正整数,证明同余方程 第 8 页,共 38 页 x2n mod p 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -有解的充要条件是n= 1；p6.设 p 是奇素数,证明：模p 的全部二次剩余的乘积与1p1对模 p 同余；2第 6 节1. 已知 769 与 1013 是素数,判定方程2 x 1742 mod 769 ；2 x 1503 mod 1013 ；是否有解；2

22、. 3. 4. 5. 6.求全部的素数p,使得下面的方程有解：2 x 11 mod p；求全部的素数p,使得 3y2 QRp, 3 QRp；2 的奇素数因数的一般形式；设x, y = 1,试求 x2证明：形如8k 5（k Z）的素数无穷多个；证明：对于任意的奇素数p,总存在整数n,使得p n22 1n 2n2 2；第 7 节1.证明定理的结论 , ,；a；的关系；2.已知 3019 是素数,判定方程2 x 374 mod 3019 是否有解；3.设奇素数为p = 4n 1 型,且 d n,证明：d= 1；p4.设 p,q 是两个不同的奇素数,且p = q 4a,证明：apq5.设 a 0,b

23、0,b 为奇数,证明：2 aab a b a b当a0,1 mod4 6.当a2,3 mod4；b 与a b设 a,b,c 是正整数, a, b = 1 ,2 | b,b 1,模 m 有原根, d 是 m的任一个正因数,证明：在模 m 的简化剩余系中,恰有 d个指数为 d 的整数,并由此推出模 m 的简化剩余系中恰有 m个原根；4. 设 m 3,g 是模 m 的原根, x1, x2, , x m是模 m 的简化剩余系,证明： m g 2 1 mod m； x1x2 x m 1 mod m；n5. 设 p = 2 1 是一个奇素数,证明：模 p 的全部二次非剩余就是模 p 的全部原根；6. 证明

24、：细心整理归纳 精选学习资料 第 10 页,共 38 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - - 设 p 奇素数,就M p = 2p 1 的素因数必为2pk 1 型； 设 n 0,就 F n =2 2n 1 的素因数必为2n+ 1k 1 型；第 2 节1.2. 3.4.5. 6.求模 29 的最小正原根；分别求模 29 3 和模 2 293 的原根；12 解同余方程： x 16 mod 17；设 p 和 q = 4p 1 都是素数,证明：2 是模 q

25、的一个原根；设 m 3,g1和 g2都是模 m 的原根,就g = g1g2 不是模 m 的原根；设 p 是奇素数,证明：当且仅当p 1 | n 时,有1n 2n p 1n 0 mod p；第 8 章第 1 节1. 补足定理 1 的证明；2. 证明定理 2；3. 证明：有理数为代数整数的充要条件是这个有理数为整数；第 2 节1.证明例中的结论；11112.证明连分数1010.23 .1010n .是超越数；3.设 是一个超越数,是一个非零的代数数,证明：,都是超越数；第 3 节1.证明引理 1；a bF0是整数；2.证明定理 3 中的 F第 9 章第 1 节1. 问： 1948 年 2 月 14

26、 日是星期几？2. 问： 1999 年 10 月 1 日是星期几？第 2 节1. 编一个有十个球队进行循环赛的程序表；2. 编一个有九个球队进行循环赛的程序表；第 3 节1.利用例 1 中的加密方法,将“ICOMETODAY ” 加密；,24,25 对应,又已知 第 11 页,共 38 页 - - - - - - - - - 2. 已知字母a,b,y,z,它们分别与整数00,01,明文 h 与 p 分别与密文e 与 g 对应,试求出密解公式：P a Eb mod 26 ,细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - -

27、 - - - - - - - - - - - -并破译下面的密文： “IRQXREFRXLGXEPQVEP” ；第 4 节1.设一 RSA 的公开加密钥为n = 943,e = 9,试将明文P = 100 加密成密文E；2. 设 RSA nA, eA = RSA33, 3 ,RSAnB, eB = RSA35, 5 ,A 的签证信息为M = 3,试说明 A 向 B 发送签证 M 的传送和认证过程；第 5 节1. 设某数据库由四个文件组成：F1 = 4,F 2 = 6,F 3 = 10,F4 = 13；试设计一个对该数据库加密的方法,但要能取出个别的 F i（ 1 i 4）,同时不影响其他文件的

28、保密；2. 利用本节中的隐秘共享方案,设计一个由三方共管文件 M = 3 的方法,要求：只要有两方供应他们所把握的数据,就可以求出文件M,但是,仅由任何一方的数据,不能求出文件M；（提示：取p = 5, m1 = 8,m2 = 9,m3 = 11）第 6 节1. 设明文 P 的二进制表示是 P = p1p2p3p4p5p6p7p82,与 P 对应的密文是 E 是 E = a1p1a2p2 a8p8,假如这里的超增背包向量 a1, a2, a3, a4, a5, a6, a7, a8 = 5, 17, 43, 71, 144, 293, 626, 1280,并且已知密文 E = 1999,求明文

29、 P；2. 给定超增背包向量 2, 3, 7, 13, 29, 59 ,试设计一个背包型加密方法,将明文 P = 51 加密；（提示：取 M = 118, k = 77）；细心整理归纳 精选学习资料 第 12 页,共 38 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -附录 1 习题参考答案第一章 习 题 一1. 由 a b 知 b = aq,于是 b = a q, b = a q及 b = aq,即 a b,a b及 a b；反之,由 a b,a b 及

30、 a b 也可得 a b； 由 a b,b c 知 b = aq1,c = bq2,于是 c = aq1q2,即 a c； 由 b ai知 ai = bqi,于是 a1x1 a2x2 akxk = bq1x1 q2x2 qkxk,即 b a1x1 a2x2 akxk； 由 b a 知 a = bq,于是 ac = bcq,即 bc ac； 由 b a 知 a = bq,于是 |a| = |b|q|,再由 a 0 得|q| 1,从而 |a| |b|,后半结论由前半结论可得；2. 由恒等式 mqnp = mnpq mpnq及条件 mp mnpq 可知 mp mqnp；3. 在给定的连续 39 个自然数的前 20 个数中,存在两个自然