《《初等数论》习题集及答案.doc》由会员分享,可在线阅读,更多相关《《初等数论》习题集及答案.doc(38页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、YOUR LOGO原 创 文 档 请 勿 盗 版精选名师资料初等数论习题集第第1 章1 节1.证明定理2.证明:若1。mp mnpq,则 mp mqnp。3.证明: 任意给定的连续39 个自然数, 其中至少存在一个自然数,使得这个自然数的数字和能被11 整除。34.设 p 是 n 的最小素约数,n = pn1, n1 1,证明:若n1 是素数。p n ,则5.证明:存在无穷多个自然数n,使得 n 不能表示为2p( a 0 是整数, p 为素数)a的形式。第 2 节1.证明: 122.设 3a43210n, nZ。n2n11n22,证明: 3a 且 3 b。bk 与nk + 4 的个位数字相同。
2、3.设 n,k 是正整数,证明:n2224.证明:对于任何整数5.设 a 是自然数,问6.证明:对于任意给定的 除。n, m,等式 n2 不可能成立。(n1)= m429 是素数还是合数?a3an 个整数,必可以从中找出若干个作和,使得这个和能被n 整第3 节1.证明定理2.证明定理3.证明定理4.设 x, y1 中的结论 ( ) ( )。2 的推论4 的推论1, 推论 2 和推论1 和推论 3。3。Z , 172x3y,证明:9x5y。17225.设 a,b, cN ,c 无平方因子,ab c,证明:a b。132 n1设 n 是正整数,求C 2n , C 2 n ,的最大公约数。6., C
3、 2 n第4 节1.证明定理1。2.证明定理3 的推论。3.设 a,b 是正整数,证明:4.求正整数a, b,使得 ab。( ab) a, b = ab, ab = 120, (a, b) = 24 , a, b = 144 。5.设 a,b, c 是正整数,证明: a, b, c 2 a, b b, c c, a( a, b, c) 2(a, b)(b, c)( c, a)。kkk。6.设 k 是正奇数,证明:5 节129129第1.说明例 1 证明中所用到的四个事实的依据。精品学习资料第 1 页,共 38 页精选名师资料2.用辗转相除法求整数x,y,使得 1387x162y = (1387
4、, 162) 。3.计算: (27090, 21672, 11352) 。4.使用引理1 中的记号,证明:(Fn + 1, Fn) = 1 。5.若四个整数2836, 4582 ,5164, 6522 被同一个大于1 的整数除所得的余数相同,且不等于零,求除数和余数各是多少?nM(a , b) 。6.记 Mn = 2第 6 节1,证明:对于正整数a, b,有 (Ma , M b) =1.证明定理1 的推论 1。2.证明定理1 的推论 2。3.写出 22345680 的标准分解式。4.证明:在, 2n 中任取 n1 数,其中至少有一个能被另一个整除。1, 2,121n5.证明: 1( n2)不是
5、整数。a1,a2 ,b1, b2,使得6.设 a,b 是正整数,证明:存在a = a1 a2,b = b1b2, (a2, b2) = 1 ,并且 a, b = a2b2。第 7 节1.证明定理1。k 整除的最大的k 值。2.求使 12347!被 352 r2r1nr 1 =3.设 n 是正整数, x 是实数,证明:n。4.设 n 是正整数,求方程222x x = ( x x)在 1, n 中的解的个数。5.证明:方程f (x) = x没有实数解。23452 x2 x2 x2 x2 x = 123456.证明: 在码之和。n! 的标准分解式中,2 的指数 h = nk,其中 k 是 n 的二进
6、制表示的位数第 8 节1.证明:若2.证明:若n1 是素数,则1 是素数,则n 是 2 的乘幂。n 是素数。2n23.证明:形如6n5 的素数有无限多个。4.设 d 是正整数, 6 | d,证明:在以d 为公差的等差数列中,连续三项都是素数的情况最多发生一次。5.证明:对于任意给定的正整数n,必存在连续的n 个自然数,使得它们都是合数。精品学习资料第 2 页,共 38 页精选名师资料1pn发散,此处使用了定理1 注2 中的记号。证明:级数6.n1第第2 章1 节1.证明定理2.证明定理3.证明定理1 和定理 2。4。5 中的结论 ( ) ( )。13 除的余数。1234 被4.求5.设 整数解
7、。8f(x)是整系数多项式,并且, f(m)都不能被m 整除,则f(x) = 0 没有f(1),f(2),已知 99427 ,求与。6.62第2 节1.证明定理2.证明:若1。2p1 是奇素数,则2p0 (mod 2 p1)。( p1),则 1 (mod N)。( p!)(1)3.证明:若p 是奇素数, N = 1(p21)!p4.证明 Wilson 定理的逆定理:若(nn 是素数。5.设 m 是整数, 4 m, a1, a2,n 1 ,并且1 (mod n),1)!则, am 与 b1, b2, bm 是模m 的两个完全剩余系,证明: a1b1, a2b2, ambm 不是模 m 的完全剩余
8、系。,mn 是两两互素的正整数,i1 (mod mi) ,i( 11j, 1n)是整数,并且n, n。iii , j6.设 m1, m2,0 (mod mj), ii证明:当bi 通过模 mi( 1in)的完全剩余系时,b1 1b2 2bn n通过模 m =第 3 节mn 的完全剩余系。m1m21.证明定理1。, mn 是两两互素的正整数,xi 分别通过模mi 的简化剩余系(1n),i2.设 m1, m2,mmimn, Mi,则m = m1m2=M 1x1M 2x2Mnxn通过模 m 的简化剩余系。3.设 m 1, (a, m) = 1 , x1 , x 2,(m)是模m 的简化剩余系,证明:
9、, x( m)ax12i ( m) 。mi 1精品学习资料第 3 页,共 38 页精选名师资料其中 x 表示 x 的小数部分。设m 与 n 是正整数,证明:(mn)(m, n) = ( m, n)(m)(n)。 a,b 是任意给定的正整数,证明:存在无穷多对正整数a ( m) = b(n)。n 是正整数,证明:4.设m 与 n,使得5.设6.12;()(n) n()若 n 是合数,则n 。(n)n第4 节1.2.3.4.1033 能被 103 整除。证明: 1978求 3131978159 被7 除的余数。560证明:对于任意的整数a, ( a, 561) = 1 ,都有 a1 (mod 56
10、1) ,但561 是合数。设 p,q 是两个不同的素数,证明:q1p11 (mod pq)。pq12将 61 分解成素因数之积。5.设 n5 节1.2.nN, bN ,对于 b1 的素因数,你有甚麽与例6 相似的结论?6.第证明例2 中的结论。证明定理2。1d |n d。求3.设f(n)是积性函数,证明:4.()( d) f ( d )(1f ( p)d |np |n2()(1f ( p) 。(d ) f ( d)d |np|n求(n)的变换。5.3 章1 节1.2.Mobius第第证明定理3。写出 789 的二进制表示和五进制表示。821的小数的循环节。求3.证明:七进制表示的整数是偶数的充
11、要条件是它的各位数字之和为偶数。4.mn的 b 进制小数 (0 a为有限小数的充要条件是n 的证明:既约正分数5.1a 2a)b3每个素因数都是第 2 节b 的素因数。精品学习资料第 4 页,共 38 页精选名师资料pkqk,证明:设连分数的第 k 个渐近分数为1.1,2,n,a1a2 101a300001000a2 101a300100001100100,pkqk00010ak11ak00010ak11ak1100pk,证明:设连分数的第 k 个渐近分数为2.1,2,n,qka1110a2110ak110pkqkpkqk1, k2。1求连分数求连分数的前三个渐近分数。的值。3.4.5.第 3
12、 节1.1, 2, 3, 4, 5,2, 3, 2, 3,解不定方程:7x9y = 4。证明定理4。求13 的连分数。2.5 的有理逼近。5 的有理逼近。求3 的误差3.210求sin18 的误差4.5.10已知圆周率,求的误差=3, 7, 15, 1, 292, 1, 1, 1, 21,6 的有理逼近。1015FkFk1连分数展开的第k 个渐近分数为。此处 F6.证明:n 是Fibonacci 数列。2第 4 节1.将方程22 = 0 的正根写成连分数。3x2x2.求1, 2, 3 之值。=23.设a 是正整数,求1 的连分数。apkqk, 证 明 :4.设 无 理 数d的 第个 渐 近 分
13、 数 为=a1,a2,an,k, an , 2a1的充要条件是da1 , a2 ,1, dqn =1。pn = a1qnqna1pnpn精品学习资料第 5 页,共 38 页精选名师资料pkqk,且正整数n 使得5.设无理数d的第 k 个渐近分数为=a1, a2, an,1, dqn =1,pn = a1qnqna1pnpn证明:()()x2x2dy= 1 的解;dy= 1 的解。pn,qn 是不定方程p2n, q2n 是不定方程当 n 为偶数时,当 n 为奇数时,22第第4 章1 节17105写成三个既约分数之和,它们的分母分别是3, 5 和 7。1.将2.求方程 x12x23x 3 = 41
14、 的所有正整数解。3.求解不定方程组:x12x12x 25 x 23x 320x 3711。4.甲班有学生7 人,乙班有学生11 人,现有100 支铅笔分给这两个班,要使甲班的学生分到相同数量的铅笔,乙班学生也分到相同数量的铅笔,问应怎样分法?5.证明:二元一次不定方程by = n,a 0 ,b 0 ,( a, b) = 1 的非负整数解的个axnn 或 数为1。abab(a1)(b21)个整6.设 a 与 b 是正整数, (a, b) = 1 ,证明: 1, 2,ab 中恰有, ab数可以表示成axby( x0, y0)的形式。第2 节1.2.3.4.5.证明定理2 推论。设 x, y, z
15、 是勾股数, x 是素数,证明: 求整数 x, y, z, x y z,使 xy, x1, 2(xy1)都是平方数。2zz, yz 都是平方数。222, x 0 , y 0, z 0 , (x, y ) = 1 。解不定方程:x3y = z证明下面的不定方程没有满足xyz0 的整数解。2222 2;( )( )xxyyz = x y222z = 2xyz。224 的满足 (x, y ) = 1 , 2 x 的正整数解。求方程 x6.3 节1.y =z第2求方程 x6 = 0 的整数解。xyxyx 3z0z3的整数解。求方程组2.y318xy求方程 23 = 1 的正整数解。3.1x1y1z求方
16、程的正整数解。4.精品学习资料第 6 页,共 38 页精选名师资料2p1x1y, a2n5.设p 是素数,求方程的整数解。1 满足条件P:其中任意2n 个数可以分成两组,6.设1 个有理数a1, a2,2n每组 n 个数,两组数的和相等,证明:a1 = a1 =1。= a2n第第5 章1 节1.证明定理1。2.解同余方程:()()5 (mod 17) ;31x3215x160 (mod 235) 。3.解同余方程组:3xx5 yy38(mod 47)10(mod 47)。4.设p 是素数, 0 a n。证明定理的推论。将例 2 中略去的部分补足。将例 4 中略去的部分补足。2解同余方程解同余方
17、程1 (mod 54) 。x20 (mod 75) 。n,必存在m,使得同余方程f(x) = 3 x4x152证明:对于任意给定的正整数1 (mod m)的解数x第 4 节1.()()2.()()3.解同余方程:11840 (mod 7) ;20 (mod 5)。3x2x5x13x201274x判定3x2x320 (mod 5) 是否有三个解;0 (mod 5) 是否有六个解?2xx3x1652x2x4x3k设 (a, m) = 1 , k 与 m 是正整数,又设a (mod m),证明同余方程m)x0kxa(modk的一切解x 都可以表示成xyx0 (mod m),其中 y 满足同余方程1
18、(mod m)。yn4.设 n 是正整数, p 是素数,5.设 p 是素数,证明:1) = k,证明同余方程1 (mod p)有 k 个解。(n, pxp1()()对于一切整数x, x1) (mod p);1(x1) ( x2)(xp1 (mod p)。(p1)!6.设 p所有的系数都是3 是素数,证明:p 的倍数。p1)的展开式中除首项及常数项外,(x1)(x2)(x第 5 节21.同余方程x3 (mod 13) 有多少个解?2.求出模 23 的所有的二次剩余和二次非剩余。3.设 p 是奇素数,证明:模p 的两个二次剩余的乘积是二次剩余;两个二次非剩余的乘积是二次剩余;一个二次剩余和一个二次
19、非剩余的乘积是二次非剩余。p 14np() = 1,证明4.设素数p3 (mod 4),n(mod p) 是同余方程x2xn (mod p)的解。5.设 p 是奇素数, (n, p) = 1 ,是正整数,证明同余方程2xn (mod p )精品学习资料第 8 页,共 38 页精选名师资料( n ) = 1 。p有解的充要条件是p 12对模p 同余。6.设 p 是奇素数,证明:模p 的所有二次剩余的乘积与(1)第 6 节1.已知769 与 1013 是素数,判定方程1742 (mod 769) ;1503 (mod 1013) 。2()() 是否有解。xx2求所有的素数p,使得下面的方程有解:2
20、.211 (mod p)。x求所有的素数p,使得2QR(p) , 3QR(p)。2 的奇素数因数的一般形式。3.4.5.6.2设 (x, y) = 1 ,试求 x3y证明:形如8k5( kZ )的素数无穷多个。证明:对于任意的奇素数p,总存在整数n,使得2222)。p(n1)( n2)(n第7 节1.2.证明定理的结论( ),( ), ( )。2已知 3019 是素数,判定方程374 (mod 3019) 是否有解。xn,证明: ( d ) = 1。p设奇素数为p = 4n1 型,且3.d( a )p( a)q设p,q 是两个不同的奇素数,且q4a,证明:。4.p =设a 0, b 0,b 为
21、奇数,证明:5.( a )b当 a0,1(mod 4)a()( a )b2ab当a2,3(mod 4) 。a4ac)与 ( a ) 的关系。b(a, b, c 是正整数, (a, b) = 1 , 2 | b,b 1,模 m 有原根, d 是(m)的任一个正因数,证明:在模2.3.中,恰有4.m 的简化剩余系(m)个原根。(d)个指数为d 的整数,并由此推出模设 m3,g 是模 m 的原根, x1, x2,( m)m 的简化剩余系中恰有, x (m)是模m 的简化剩余系,证明:2()()5.6.1 (mod m);g1 (mod m)。x1x2设 p = 2证明:x(m)n1 是一个奇素数,证
22、明:模p 的全部二次非剩余就是模p 的全部原根。精品学习资料第 10 页,共 38 页精选名师资料p()设p 奇素数,则1 的素因数必为2pk1 型;Mp = 22 nn +1( )设n0,则 Fn =21 的素因数必为1 型。2k第2 节1.求模29 的最小正原根。3 和模 2 293 的原根。2.分别求模29123.解同余方程:x16 (mod 17) 。4.设5.设6.设p 和 q = 4 p1 都是素数,证明:2 是模 q 的一个原根。m3,g1 和g2 都是模 m 的原根,则g = g1g2 不是模m 的原根。p 是奇素数,证明:当且仅当1 | n 时,有p(pnnn0 (mod p
23、)。121)第第8 章1 节1.补足定理1 的证明。2.证明定理2。3.证明:有理数为代数整数的充要条件是这个有理数为整数。2 节1.证明例中的结论。2.证明连分数第110111012!3!n!1010是超越数。都是超越数。3.设 是一个超越数,是一个非零的代数数,证明:,第3 节1.证明引理 1。a2.证明定理 3 中的 F ()b9 章1 节F(0) 是整数。第第1.问: 1948 年 2 月 14 日是星期几?2.问: 1999 年 10 月 1 日是星期几?2 节1.编一个有十个球队进行循环赛的程序表。2.编一个有九个球队进行循环赛的程序表。3 节第第1.利用例 1 中的加密方法,将“
24、ICOMETODAY”加密。2.已知字母a, b, y, z,它们分别与整数00, 01, 24,25 对应,又已知明文 h 与 p 分别与密文e 与 g 对应,试求出密解公式:b(mod 26) ,Pa E精品学习资料第 11 页,共 38 页精选名师资料并破译下面的密文: “ IRQXREFRXLGXEPQVEP第 4 节”。1.设一RSA 的公开加密钥为n = 943, e = 9,试将明文P = 100 加密成密文E。M = 3 ,2.设 RSA( nA, eA) = RSA(33, 3) , RSA( nB, eB) = RSA(35, 5) , A 的签证信息为试说明 A 向 B
25、发送签证M 的传送和认证过程。 第 5 节1.设某数据库由四个文件组成:数据库加密的方法,但要能取出个别的F1 = 4 ,F 2 = 6 , F 3 = 10, F4 = 13。试设计一个对该F i( 1i4),同时不影响其他文件的保密。2.利用本节中的秘密共享方案,设计一个由三方共管文件M = 3 的方法,要求:只要有两方提供他们所掌握的数据,就可以求出文件M,但是,仅由任何一方的数据,不能求出文件M 。(提示:取p = 5, m1= 8 ,m2 = 9 , m3 = 11)第 6 节1.设明文 P 的二进制表示是P = (p1p2p3p4p5p6p7p8)2,与P 对应的密文是E 是 E
26、=a1p1a8p8,如果这里的超增背包向量(a1, a2, a3, a4, a5, a6 , a7, a8) = (5, 17, 43, 71, 144,a2p2293, 626, 1280) ,并且已知密文E = 1999 ,求明文P。2.给定超增背包向量(2, 3, 7, 13, 29, 59) ,试设计一个背包型加密方法,将明文P = 51 加密。(提示:取M = 118, k = 77)。精品学习资料第 12 页,共 38 页精选名师资料附录 1 习题参考答案第一章习 题一( )由 ab 知ab = aq,于是a)(q) ,b 也可得b = a(q)及b = (a)q,即a由 ab,
27、b c 知b,a1.及 ab = (a( )bb。反之,由b,ab 及c; a1x1ab;( )b = aq1,akxk =c = bq2,于是b( q1x1q2 x2即 bcac;由 bai 知=akxk ;( )aibqi,于是c =a(q1q2),即 aqkxk ),即 ba1x1a2x2由ab a 知 a = bq,于是ac = bcq,a2 x2( )由 b a 知a = bq,于是|a| = |b|q|,再由0 得 |q|1,从而 |a|b |,后半结论由前半结论可得。2.由恒等式 mq np。p)(nq)及条件 mp mnpq 可知 mnp = ( mnpq)( mpmq3.在给
28、定的连续39 个自然数的前20 个数中,存在两个自然数, 它们的个位数字是0,a其中必有一个的十位数字不是9,记这个数为a,它的数字和为s,则 a, a1, a9,19 的数字和为9, s10,其中必有一个能被11 整除。s, s1, sp3,即 p4.设不然, n1 = n2n3, n23p, n3p,于是 n = pn2n3,矛盾。n2 不能表示为a215.存在无穷多个正整数k,使得2k1 是合数,对于这样的k,(k1)22p 的形式, 事实上, 若 (kp,则(ka) = p,得a = 1 ,k1)= a1a)( k1k1a = p,即 p = 2 k1,此与 p 为素数矛盾。第一章习
29、题 二1.验证当 n =0,1, 2,,11 时, 12|f( n)。r2,r 1, r2 = 0, 1 或 2,由 32a2b = 3 Q22 知r 1,b = 3q2r2.写 a = 3q1r 1r21 = r 2 =0,即3a 且3b。k+4k 被rk+4kk410 除的余数和3.记 n=10 q+r , (r=0,1,9,) 则 n- nr ( r -1) 被 10 除的-r=余数相同。对,9进行验证即可。r=0,1,2224.对于任何整数n, m,等式 n2 的左边被4 除的余数为1,而右边(n1)= m被 4 除的余数为2 或3,故它不可能成立。42222425因3),当a = 1
30、,2 时, a3 = 1, aa3a9 = ( a3a3)( a3a3a3a242223 = 7,13,a9 是素数;当3 时, a3a3 1 ,a3a3 1,9 = a3a3aa429 是合数。a3a, an,作6.设给定的 n 个整数为a1, a2,s1 = a1, s2 = a1a2, snan,j,使得 si 与 sj 被= a1a2如果 si 中有一个被n 整除,则结论已真,否则存在si, sj ,in 除的余数相等,于是。nsjsi =ai + 1aj精品学习资料第 13 页,共 38 页精选名师资料第一章习 题 三ak 的公约数的集合与|a 1|, |a2|,1.( )因为 da
31、 和 d|a| 是等价的,所以a1, a2,|ak| 的公约数的集合相同,所以它们的最大公约数相等;( ),( )显然;( )pa。设d,则( )d p, d a,由d p 得或d = p,前者推出(p, a) = 1,后者推出(p, a) =2.kd = 1ai 推出y0 和 Y0 表示集合 A = y;k 中的最小正整数,显dy0由, ak);( )分别以d= ( a1, a2,k= y; y =mai xi*,xi,xiZ ,k 和 AZ ,y =iia i x ii 1i1aaa然有 Y0= |m|y0;( )在推论2 中取 m =,并用12k, ak 即可。代替 a1, a2,若 p | a,则(p, a)( )1,从而由ab 推出p b;( )在 ( )中取 a = b 可得;3.=p( )= ( a, bn) = 1。5y) = 17y 及 172x3y 得(a, b1b2bn) = (a, b2bn) =2(9x4.由恒等式故 179x5y。5.设 (a, b) = c 无平方因子,所以5y),又 (17, 2) = 1 ,9(2x3y)172(9x22222da1, b =db1, (a1, b1) = 1 ,由 ab c 得d,则 a =b1 c, a1c,因为a1a1 = 1, a = d,b = ab1,即b。a2n 1kk+1132n 1132n
限制150内