《初等数论》习题解答.docx

《初等数论》习题解答.docx

《《初等数论》习题解答.docx》由会员分享，可在线阅读，更多相关《《初等数论》习题解答.docx（20页珍藏版）》请在冰点文库上搜索。

《初等数论》习题解答

《初等数论》习题集

第1章

第1节

1.证明定理1。

2.证明：

若mpmnpq，则mpmqnp。

3.证明：

任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。

4.设p是n的最小素约数，n=pn1，n1>1，证明：

若p>

，则n1是素数。

5.证明：

存在无穷多个自然数n，使得n不能表示为

a2p（a>0是整数，p为素数）

的形式。

第2节

1.证明：

12n42n311n210n，nZ。

2.设3a2b2，证明：

3a且3b。

3.设n，k是正整数，证明：

nk与nk+4的个位数字相同。

4.证明：

对于任何整数n，m，等式n2（n1）2=m22不可能成立。

5.设a是自然数，问a43a29是素数还是合数？

6.证明：

对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。

第3节

1.证明定理1中的结论（ⅰ）—（ⅳ）。

2.证明定理2的推论1,推论2和推论3。

3.证明定理4的推论1和推论3。

4.设x，yZ，172x3y，证明：

179x5y。

5.设a，b，cN，c无平方因子，a2b2c，证明：

ab。

6.设n是正整数，求

的最大公约数。

第4节

1.证明定理1。

2.证明定理3的推论。

3.设a，b是正整数，证明：

（ab）[a,b]=a[b,ab]。

4.求正整数a，b，使得ab=120，（a,b）=24，[a,b]=144。

5.设a，b，c是正整数，证明：

。

6.设k是正奇数，证明：

1291k2k9k。

第5节

1.说明例1证明中所用到的四个事实的依据。

2.用辗转相除法求整数x，y，使得1387x162y=（1387,162）。

3.计算：

（27090,21672,11352）。

4.使用引理1中的记号，证明：

（Fn+1,Fn）=1。

5.若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少？

6.记Mn=2n1，证明：

对于正整数a，b，有（Ma,Mb）=M（a,b）。

第6节

1.证明定理1的推论1。

2.证明定理1的推论2。

3.写出22345680的标准分解式。

4.证明：

在1,2,,2n中任取n1数，其中至少有一个能被另一个整除。

5.证明：

（n2）不是整数。

6.设a，b是正整数，证明：

存在a1，a2，b1，b2，使得

a=a1a2，b=b1b2，（a2,b2）=1，

并且[a,b]=a2b2。

第7节

1.证明定理1。

2.求使12347!

被35k整除的最大的k值。

3.设n是正整数，x是实数，证明：

=n。

4.设n是正整数，求方程

x2[x2]=（x[x]）2

在[1,n]中的解的个数。

5.证明：

方程

f（x）=[x][2x][22x][23x][24x][25x]=12345

没有实数解。

6.证明：

在n!

的标准分解式中，2的指数h=nk，其中k是n的二进制表示的位数码之和。

第8节

1.证明：

若2n1是素数，则n是2的乘幂。

2.证明：

若2n1是素数，则n是素数。

3.证明：

形如6n5的素数有无限多个。

4.设d是正整数，6

d，证明：

在以d为公差的等差数列中，连续三项都是素数的情况最多发生一次。

5.证明：

对于任意给定的正整数n，必存在连续的n个自然数，使得它们都是合数。

6.证明：

级数

发散，此处使用了定理1注2中的记号。

第2章

第1节

1.证明定理1和定理2。

2.证明定理4。

3.证明定理5中的结论（ⅰ）—（ⅳ）。

4.求81234被13除的余数。

5.设f（x）是整系数多项式，并且f

（1）,f

（2）,,f（m）都不能被m整除，则f（x）=0没有整数解。

6.已知99

，求与。

第2节

1.证明定理1。

2.证明：

若2p1是奇素数，则

（p!

）2

（1）p0（mod2p1）。

3.证明：

若p是奇素数，N=12（p1），则

（p1）!

p1（modN）。

4.证明Wilson定理的逆定理：

若n>1，并且

（n1）!

1（modn），

则n是素数。

5.设m是整数，4m，{a1,a2,,am}与{b1,b2,,bm}是模m的两个完全剩余系，证明：

{a1b1,a2b2,,ambm}不是模m的完全剩余系。

6.设m1,m2,,mn是两两互素的正整数，i（1in）是整数，并且

i1（modmi），1in，

i0（modmj），ij，1i,jn。

证明：

当bi通过模mi（1in）的完全剩余系时，

b11b22bnn

通过模m=m1m2mn的完全剩余系。

第3节

1.证明定理1。

2.设m1,m2,,mn是两两互素的正整数，xi分别通过模mi的简化剩余系（1in），m=m1m2mn，Mi=

，则

M1x1M2x2Mnxn

通过模m的简化剩余系。

3.设m>1，（a,m）=1，x1,x2,,x（m）是模m的简化剩余系，证明：

。

其中{x}表示x的小数部分。

4.设m与n是正整数，证明：

（mn）（（m,n））=（m,n）（m）（n）。

5.设a，b是任意给定的正整数，证明：

存在无穷多对正整数m与n，使得

a（m）=b（n）。

6.设n是正整数，证明：

（ⅰ）（n）>

；

（ⅱ）若n是合数，则（n）n

。

第4节

1.证明：

197810319783能被103整除。

2.求313159被7除的余数。

3.证明：

对于任意的整数a，（a,561）=1，都有a5601（mod561），但561是合数。

4.设p，q是两个不同的素数，证明：

pq1qp11（modpq）。

5.将6121分解成素因数之积。

6.设nN，bN，对于bn1的素因数，你有甚麽与例6相似的结论？

第5节

1.证明例2中的结论。

2.证明定理2。

3.求

。

4.设f（n）是积性函数，证明：

（ⅰ）

（ⅱ）

。

5.求（n）的Mobius变换。

第3章

第1节

1.证明定理3。

2.写出789的二进制表示和五进制表示。

3.求

的小数的循环节。

4.证明：

七进制表示的整数是偶数的充要条件是它的各位数字之和为偶数。

5.证明：

既约正分数

的b进制小数（0a1a2a3）b为有限小数的充要条件是n的每个素因数都是b的素因数。

第2节

1.设连分数1,2,,n,的第k个渐近分数为

，证明：

，

2.设连分数1,2,,n,的第k个渐近分数为

，证明：

，k2。

3.求连分数1,2,3,4,5,的前三个渐近分数。

4.求连分数2,3,2,3,的值。

5.解不定方程：

7x9y=4。

第3节

1.证明定理4。

2.求

的连分数。

3.求

的误差105的有理逼近。

4.求sin18的误差105的有理逼近。

5.已知圆周率=3,7,15,1,292,1,1,1,21,，求的误差

106的有理逼近。

6.证明：

连分数展开的第k个渐近分数为

。

此处{Fn}是Fibonacci数列。

第4节

1.将方程3x22x2=0的正根写成连分数。

2.求=

之值。

3.设a是正整数，求

的连分数。

4.设无理数

=a1,a2,,an,的第k个渐近分数为

，证明：

的充要条件是

pn=a1qnqn1，dqn=a1pnpn1。

5.设无理数

=a1,a2,,an,的第k个渐近分数为

，且正整数n使得

pn=a1qnqn1，dqn=a1pnpn1，

证明：

（ⅰ）当n为偶数时，pn，qn是不定方程x2dy2=1的解；

（ⅱ）当n为奇数时，p2n，q2n是不定方程x2dy2=1的解。

第4章

第1节

1.将

写成三个既约分数之和，它们的分母分别是3，5和7。

2.求方程x12x23x3=41的所有正整数解。

3.求解不定方程组：

。

4.甲班有学生7人，乙班有学生11人，现有100支铅笔分给这两个班，要使甲班的学生分到相同数量的铅笔，乙班学生也分到相同数量的铅笔，问应怎样分法？

5.证明：

二元一次不定方程axby=n，a>0，b>0，（a,b）=1的非负整数解的个数为

1。

6.设a与b是正整数，（a,b）=1，证明：

1,2,,abab中恰有

个整数可以表示成axby（x0，y0）的形式。

第2节

1.证明定理2推论。

2.设x，y，z是勾股数，x是素数，证明：

2z1，2（xy1）都是平方数。

3.求整数x，y，z，x>y>z，使xy，xz，yz都是平方数。

4.解不定方程：

x23y2=z2，x>0，y>0，z>0，（x,y）=1。

5.证明下面的不定方程没有满足xyz0的整数解。

（ⅰ）x2y2z2=x2y2；

（ⅱ）x2y2z2=2xyz。

6.求方程x2y2=z4的满足（x,y）=1，2x的正整数解。

第3节

1.求方程x2xy6=0的整数解。

2.求方程组

的整数解。

3.求方程2x3y=1的正整数解。

4.求方程

的正整数解。

5.设p是素数，求方程

的整数解。

6.设2n1个有理数a1,a2,,a2n1满足条件P：

其中任意2n个数可以分成两组，每组n个数，两组数的和相等，证明：

a1=a1==a2n1。

第5章

第1节

1.证明定理1。

2.解同余方程：

（ⅰ）31x5（mod17）；

（ⅱ）3215x160（mod235）。

3.解同余方程组：

。

4.设p是素数，0

（modp）。

是同余方程axb（modp）的解。

5.证明：

同余方程a1x1a2x2anxnb（modm）有解的充要条件是

（a1,a2,,an,m）=db。

若有解，则恰有dmn1个解，modm。

6.解同余方程：

2x7y5（mod12）。

第2节

1.解同余方程组：

2.解同余方程组：

3.有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。

已知这队士兵不超过170人，问这队士兵有几人？

4.求一个最小的自然数n，使得它的

是一个平方数，它的

是一个立方数，它的

是一个5次方数。

5.证明：

对于任意给定的n个不同的素数p1,p2,…,pn，必存在连续n个整数，使得它们中的第k个数能被pk整除。

6.解同余方程：

3x211x200（mod105）。

第3节

1.证明定理的推论。

2.将例2中略去的部分补足。

3.将例4中略去的部分补足。

4.解同余方程x21（mod54）。

5.解同余方程f（x）=3x24x150（mod75）。

6.证明：

对于任意给定的正整数n，必存在m，使得同余方程x21（modm）的解数T>n。

第4节

1.解同余方程：

（ⅰ）3x112x85x410（mod7）；

（ⅱ）4x203x122x73x20（mod5）。

2.判定

（ⅰ）2x3x23x10（mod5）是否有三个解；

（ⅱ）x62x54x230（mod5）是否有六个解？

3.设（a,m）=1，k与m是正整数，又设x0ka（modm），证明同余方程

xka（modm）

的一切解x都可以表示成xyx0（modm），其中y满足同余方程yk1（modm）。

4.设n是正整数，p是素数，（n,p1）=k，证明同余方程xn1（modp）有k个解。

5.设p是素数，证明：

（ⅰ）对于一切整数x，xp11（x1）（x2）（xp1）（modp）；

（ⅱ）（p1）!

1（modp）。

6.设p3是素数，证明：

（x1）（x2）（xp1）的展开式中除首项及常数项外，所有的系数都是p的倍数。

第5节

1.同余方程x23（mod13）有多少个解？

2.求出模23的所有的二次剩余和二次非剩余。

3.设p是奇素数，证明：

模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。

4.设素数p3（mod4），

=1，证明x

（modp）是同余方程

x2n（modp）

的解。

5.设p是奇素数，（n,p）=1，是正整数，证明同余方程

x2n（modp）

有解的充要条件是

=1。

6.设p是奇素数，证明：

模p的所有二次剩余的乘积与

对模p同余。

第6节

1.已知769与1013是素数，判定方程

（ⅰ）x21742（mod769）；

（ⅱ）x21503（mod1013）。

是否有解。

2.求所有的素数p，使得下面的方程有解：

x211（modp）。

3.求所有的素数p，使得2QR（p），3QR（p）。

4.设（x,y）=1，试求x23y2的奇素数因数的一般形式。

5.证明：

形如8k5（kZ）的素数无穷多个。

6.证明：

对于任意的奇素数p，总存在整数n，使得

p（n21）（n22）（n22）。

第7节

1.证明定理的结论（ⅱ），（ⅲ），（ⅳ）。

2.已知3019是素数，判定方程x2374（mod3019）是否有解。

3.设奇素数为p=4n1型，且dn，证明：

=1。

4.设p，q是两个不同的奇素数，且p=q4a，证明：

。

5.设a>0，b>0，b为奇数，证明：

6.设a，b，c是正整数，（a,b）=1，2

b，b<4ac，求

的关系。

第6章

第1节

1.设n是正整数，证明：

不定方程x2y2=zn总有正整数解x，y，z。

2.设p是奇素数，（k,p）=1，则

，

此处

是Legender符号。

3.设素数p1（mod4），（k,p）=1，记

，

则2S（k），并且，对于任何整数t，有

，

此处

是Legender符号。

4.设p是奇素数，

，则

构成模p的一个简化剩余系。

5.在第3题的条件下，并沿用第2题的记号，有

。

即上式给出了形如4k1的素数的二平方和表示的具体方法。

6.利用题5的结论，试将p=13写成二平方和。

第2节

1.若（x,y,z）=1，则不存在整数n，使得

x2y2z2=4n2。

2.设k是非负整数，证明2k不能表示三个正整数平方之和。

3.证明：

每一个正整数n必可以表示为5个立方数的代数和。

4.证明：

16k15型的整数至少需要15个四次方数的和表之。

5.证明：

16k31不能表示为15个四次方数的和。

第7章

第1节

2.求模14的全部原根。

3.设m>1，模m有原根，d是（m）的任一个正因数，证明：

在模m的简化剩余系中，恰有（d）个指数为d的整数，并由此推出模m的简化剩余系中恰有（（m））个原根。

4.设m3，g是模m的原根，x1,x2,,x（m）是模m的简化剩余系，证明：

（ⅰ）

1（modm）；

（ⅱ）x1x2x（m）1（modm）。

5.设p=2n1是一个奇素数，证明：

模p的全部二次非剩余就是模p的全部原根。

6.证明：

（ⅰ）设p奇素数，则Mp=2p1的素因数必为2pk1型；

（ⅱ）设n0，则Fn=

1的素因数必为2n+1k1型。

第2节

1.求模29的最小正原根。

2.分别求模293和模2293的原根。

3.解同余方程：

x1216（mod17）。

4.设p和q=4p1都是素数，证明：

2是模q的一个原根。

5.设m3，g1和g2都是模m的原根，则g=g1g2不是模m的原根。

6.设p是奇素数，证明：

当且仅当p1

n时，有

1n2n（p1）n0（modp）。

第8章

第1节

1.补足定理1的证明。

2.证明定理2。

3.证明：

有理数为代数整数的充要条件是这个有理数为整数。

第2节

1.证明例中的结论。

2.证明连分数

是超越数。

3.设是一个超越数，是一个非零的代数数，证明：

，，

都是超越数。

第3节

1.证明引理1。

2.证明定理3中的F

F（0）是整数。

第9章

第1节

1.问：

1948年2月14日是星期几？

2.问：

1999年10月1日是星期几？

第2节

1.编一个有十个球队进行循环赛的程序表。

2.编一个有九个球队进行循环赛的程序表。

第3节

1.利用例1中的加密方法，将“ICOMETODAY”加密。

2.已知字母a，b，，y，z，它们分别与整数00，01，，24，25对应，又已知明文h与p分别与密文e与g对应，试求出密解公式：

PaEb（mod26），

并破译下面的密文：

“IRQXREFRXLGXEPQVEP”。

第4节

1.设一RSA的公开加密钥为n=943，e=9，试将明文P=100加密成密文E。

2.设RSA（nA,eA）=RSA（33,3），RSA（nB,eB）=RSA（35,5），A的签证信息为M=3，试说明A向B发送签证M的传送和认证过程。

第5节

1.设某数据库由四个文件组成：

F1=4，F2=6，F3=10，F4=13。

试设计一个对该数据库加密的方法，但要能取出个别的Fi（1i4），同时不影响其他文件的保密。

2.利用本节中的秘密共享方案，设计一个由三方共管文件M=3的方法，要求：

只要有两方提供他们所掌握的数据，就可以求出文件M，但是，仅由任何一方的数据，不能求出文件M。

（提示：

取p=5，m1=8，m2=9，m3=11）

第6节

1.设明文P的二进制表示是P=（p1p2p3p4p5p6p7p8）2，与P对应的密文是E是E=a1p1a2p2a8p8，如果这里的超增背包向量（a1,a2,a3,a4,a5,a6,a7,a8）=（5,17,43,71,144,293,626,1280），并且已知密文E=1999，求明文P。

2.给定超增背包向量（2,3,7,13,29,59），试设计一个背包型加密方法，将明文P=51加密。

（提示：

取M=118，k=77）。