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

《初等数论》习题集
第1章
第 1 节
1. 证明定理1。
2. 证明：若m - p½mn + pq，则m - p½mq + np。
3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。
4. 设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >，则n1是素数。
5. 证明：存在无穷多个自然数n，使得n不能表示为
a2 + p（a > 0是整数，p为素数）
的形式。

第 2 节
1. 证明：12½n4 + 2n3 + 11n2 + 10n，nÎZ。
2. 设3½a2 + b2，证明：3½a且3½b。
3. 设n，k是正整数，证明：nk与nk + 4的个位数字相同。
4. 证明：对于任何整数n，m，等式n2 + (n + 1)2 = m2 + 2不可能成立。
5. 设a是自然数，问a4 - 3a2 + 9是素数还是合数？
6. 证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。
第 3 节
1. 证明定理1中的结论(ⅰ)—(ⅳ)。
2. 证明定理2的推论1, 推论2和推论3。
3. 证明定理4的推论1和推论3。
4. 设x，yÎZ，17½2x + 3y，证明：17½9x + 5y。
5. 设a，b，cÎN，c无平方因子，a2½b2c，证明：a½b。
6. 设n是正整数，求的最大公约数。
第 4 节
1. 证明定理1。
2. 证明定理3的推论。
3. 设a，b是正整数，证明：(a + b)[a, b] = a[b, a + b]。
4. 求正整数a，b，使得a + b = 120，(a, b) = 24，[a, b] = 144。
5. 设a，b，c是正整数，证明：
。
6. 设k是正奇数，证明：1 + 2 + L + 9½1k + 2k + L + 9k。

第 5 节
1. 说明例1证明中所用到的四个事实的依据。
2. 用辗转相除法求整数x，y，使得1387x - 162y = (1387, 162)。
3. 计算：(27090, 21672, 11352)。
4. 使用引理1中的记号，证明：(Fn + 1, Fn) = 1。
5. 若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少？
6. 记Mn = 2n - 1，证明：对于正整数a，b，有(Ma, Mb) = M(a, b)。

第 6 节
1. 证明定理1的推论1。
2. 证明定理1的推论2。
3. 写出22345680的标准分解式。
4. 证明：在1, 2, L, 2n中任取n + 1数，其中至少有一个能被另一个整除。
5. 证明：（n ³ 2）不是整数。
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 = n - k，其中k是n的二进制表示的位数码之和。

第 8 节
1. 证明：若2n + 1是素数，则n是2的乘幂。
2. 证明：若2n - 1是素数，则n是素数。
3. 证明：形如6n + 5的素数有无限多个。
4. 设d 是正整数，6d，证明：在以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), L, f(m)都不能被m整除，则f(x) = 0没有整数解。
6. 已知99½，求a与b。
第 2 节
1. 证明定理1。
2. 证明：若2p + 1是奇素数，则
(p!)2 + (-1)p º 0 (mod 2p + 1)。
3. 证明：若p是奇素数，N = 1 + 2 + L + ( p - 1)，则
(p - 1)! º p - 1 (mod N)。
4. 证明Wilson定理的逆定理：若n > 1，并且
(n - 1)! º -1 (mod n)，
则n是素数。
5. 设m是整数，4½m，{a1, a2, L, am}与{b1, b2, L, bm}是模m的两个完全剩余系，证明：{a1b1, a2b2, L, ambm}不是模m的完全剩余系。
6. 设m1, m2, L,mn是两两互素的正整数，di（1 £ i £ n）是整数，并且
di º 1 (mod mi)， 1 £ i £ n，
di º 0 (mod mj)，i ¹ j，1 £ i, j £ n。
证明：当bi通过模mi（1 £ i £ n）的完全剩余系时，
b1d1 + b2d2 + L + bndn
通过模m = m1m2Lmn的完全剩余系。

第 3 节
1. 证明定理1。
2. 设m1, m2, L, mn是两两互素的正整数，xi分别通过模mi的简化剩余系（1 £ i £ n），m = m1m2Lmn，Mi =，则
M1x1 + M2x2 + L + Mnxn
通过模m的简化剩余系。
3. 设m > 1，(a, m) = 1，x1, x2, ¼, xj(m)是模m的简化剩余系，证明：
。
其中{x}表示x的小数部分。
4. 设m与n是正整数，证明：
j(mn)j((m, n)) = (m, n)j(m)j(n)。
5. 设a，b是任意给定的正整数，证明：存在无穷多对正整数m与n，使得
aj(m) = bj(n)。
6. 设n是正整数，证明：
(ⅰ) j(n) >；
(ⅱ) 若n是合数，则j(n) £ n -。

第 4 节
1. 证明：1978103 - 19783能被103整除。
2. 求313159被7除的余数。
3. 证明：对于任意的整数a，(a, 561) = 1，都有a560 º 1 (mod 561)，但561是合数。
4. 设p，q是两个不同的素数，证明：
pq - 1 + qp - 1 º 1 (mod pq)。
5. 将612 - 1分解成素因数之积。
6. 设nÎN，bÎN，对于bn + 1的素因数，你有甚麽与例6相似的结论？
第 5 节
1. 证明例2中的结论。
2. 证明定理2。
3. 求。
4. 设f(n)是积性函数，证明：
(ⅰ)
(ⅱ) 。
5. 求j(n)的Mobius变换。
第3章
第 1 节
1. 证明定理3。
2. 写出789的二进制表示和五进制表示。
3. 求的小数的循环节。
4. 证明：七进制表示的整数是偶数的充要条件是它的各位数字之和为偶数。
5. 证明：既约正分数的b进制小数(0.a-1a-2a-3L)b为有限小数的充要条件是n的每个素因数都是b的素因数。
第 2 节
1. 设连分数á a1, a2, L, an, L ñ的第k个渐近分数为，证明：
，
2. 设连分数á a1, a2, L, an, L ñ的第k个渐近分数为，证明：
，k ³ 2。
3. 求连分数á 1, 2, 3, 4, 5, L ñ的前三个渐近分数。
4. 求连分数á 2, 3, 2, 3, L ñ的值。
5. 解不定方程：7x - 9y = 4。

第 3 节
1. 证明定理4。
2. 求的连分数。
3. 求的误差£ 10 - 5的有理逼近。
4. 求sin18°的误差£ 10 - 5的有理逼近。
5. 已知圆周率p = á 3, 7, 15, 1, 292, 1, 1, 1, 21, L ñ，求p的误差
£ 10 - 6的有理逼近。
6. 证明：连分数展开的第k个渐近分数为。此处{Fn}是Fibonacci数列。
第 4 节
1. 将方程3x2 + 2x - 2 = 0的正根写成连分数。
2. 求a = áñ之值。
3. 设a是正整数，求的连分数。
4. 设无理数= á a1, a2, L, an, L ñ的第k个渐近分数为，证明：的充要条件是
pn = a1qn + qn -1，dqn = a1pn + pn -1。
5. 设无理数= á a1, a2, L, an, L ñ的第k个渐近分数为，且正整数n使得
pn = a1qn + qn -1，dqn = a1pn + pn -1，
证明：
(ⅰ) 当n为偶数时，pn，qn是不定方程x2 - dy2 = 1的解；
(ⅱ) 当n为奇数时，p2n，q2n是不定方程x2 - dy2 = 1的解。

第4章
第 1 节
1. 将写成三个既约分数之和，它们的分母分别是3，5和7。
2. 求方程x1 + 2x2 + 3x3 = 41的所有正整数解。
3. 求解不定方程组：
。
4. 甲班有学生7人，乙班有学生11人，现有100支铅笔分给这两个班，要使甲班的学生分到相同数量的铅笔，乙班学生也分到相同数量的铅笔，问应怎样分法？
5. 证明：二元一次不定方程ax + by = n，a > 0，b > 0，(a, b) = 1的非负整数解的个数为+ 1。
6. 设a与b是正整数，(a, b) = 1，证明：1, 2, L, ab - a - b中恰有个整数可以表示成ax + by（x ³ 0，y ³ 0）的形式。
第 2 节
1. 证明定理2推论。
2. 设x，y，z是勾股数，x是素数，证明：2z - 1，2(x + y + 1)都是平方数。
3. 求整数x，y，z，x > y > z，使x - y，x - z，y - z都是平方数。
4. 解不定方程：x2 + 3y2 = z2，x > 0，y > 0，z > 0，(x, y ) = 1。
5. 证明下面的不定方程没有满足xyz ¹ 0的整数解。
(ⅰ) x2 + y2 + z2 = x2y2；
(ⅱ) x2 + y2 + z2 = 2xyz。
6. 求方程x2 + y2 = z4的满足(x, y ) = 1，2½x的正整数解。
第 3 节
1. 求方程x2 + xy - 6 = 0的整数解。
2. 求方程组的整数解。
3. 求方程2x - 3y = 1的正整数解。
4. 求方程的正整数解。
5. 设p是素数，求方程的整数解。
6. 设2n + 1个有理数a1, a2, L, a2n + 1满足条件P：其中任意2n个数可以分成两组，每组n个数，两组数的和相等，证明：
a1 = a1 = L = a2n + 1。

第5章
第 1 节
1. 证明定理1。
2. 解同余方程：
(ⅰ) 31x º 5 (mod 17)；
(ⅱ) 3215x º 160 (mod 235)。
3. 解同余方程组：
。
4. 设p是素数，0 < a < p，证明：
(mod p)。
是同余方程ax º b (mod p)的解。
5. 证明：同余方程a1x1 + a2x2 + L + anxn º b (mod m)有解的充要条件是
(a1, a2, L, an, m) = d½b。
若有解，则恰有d×mn -1个解，mod m。
6. 解同余方程：2x + 7y º 5 (mod 12)。
第 2 节
1. 解同余方程组：
2. 解同余方程组：
3. 有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？
4. 求一个最小的自然数n，使得它的是一个平方数，它的是一个立方数，它的是一个5次方数。
5. 证明：对于任意给定的n个不同的素数p1, p2, …, pn，必存在连续n个整数，使得它们中的第k个数能被pk整除。
6. 解同余方程：3x2 + 11x - 20 º 0 (mod 105)。

第 3 节
1. 证明定理的推论。
2. 将例2中略去的部分补足。
3. 将例4中略去的部分补足。
4. 解同余方程x2 º -1 (mod 54)。
5. 解同余方程f(x) = 3x2 + 4x - 15 º 0 (mod 75)。
6. 证明：对于任意给定的正整数n，必存在m，使得同余方程x2 º 1 (mod m)的解数T > n。

第 4 节
1. 解同余方程：
(ⅰ) 3x11 + 2x8 + 5x4 - 1 º 0 (mod 7)；
(ⅱ) 4x20 + 3x12 + 2x7 + 3x - 2 º 0 (mod 5)。
2. 判定
(ⅰ) 2x3 - x2 + 3x - 1 º 0 (mod 5)是否有三个解；
(ⅱ) x6 + 2x5 - 4x2 + 3 º 0 (mod 5)是否有六个解？
3. 设(a, m) = 1，k与m是正整数，又设x0k º a (mod m)，证明同余方程
xk º a(mod m)
的一切解x都可以表示成x º yx0 (mod m)，其中y满足同余方程yk º 1 (mod m)。
4. 设n是正整数，p是素数，(n, p - 1) = k，证明同余方程xn º 1 (mod p)有k个解。
5. 设p是素数，证明：
(ⅰ) 对于一切整数x，xp - 1 - 1 º (x - 1) (x - 2)L(x - p + 1) (mod p)；
(ⅱ) (p - 1)! º - 1 (mod p)。
6. 设p ³ 3是素数，证明：(x - 1)(x - 2)L(x - p + 1)的展开式中除首项及常数项外，所有的系数都是p的倍数。

第 5 节
1. 同余方程x2 º 3 (mod 13)有多少个解？
2. 求出模23的所有的二次剩余和二次非剩余。
3. 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。
4. 设素数 p º 3 (mod 4)，= 1，证明x º ±(mod p)是同余方程
x2 º n (mod p)
的解。
5. 设p是奇素数，(n, p) = 1，a是正整数，证明同余方程
x2 º n (mod pa)
有解的充要条件是= 1。
6. 设p是奇素数，证明：模p的所有二次剩余的乘积与对模p同余。

第 6 节
1. 已知769与1013是素数，判定方程
(ⅰ) x2 º 1742 (mod 769)；
(ⅱ) x2 º 1503 (mod 1013)。
是否有解。
2. 求所有的素数p，使得下面的方程有解：
x2 º 11 (mod p)。
3. 求所有的素数p，使得 -2ÎQR(p)，-3ÎQR(p)。
4. 设(x, y) = 1，试求x2 - 3y2的奇素数因数的一般形式。
5. 证明：形如8k + 5（kÎZ）的素数无穷多个。
6. 证明：对于任意的奇素数p，总存在整数n，使得
p½(n2 + 1)(n2 + 2)(n2 - 2)。

第 7 节
1. 证明定理的结论(ⅱ)，(ⅲ)，(ⅳ)。
2. 已知3019是素数，判定方程x2 º 374 (mod 3019)是否有解。
3. 设奇素数为p = 4n + 1型，且d½n，证明：= 1。
4. 设p，q是两个不同的奇素数，且p = q + 4a，证明：。
5. 设a > 0，b > 0，b为奇数，证明：

6. 设a，b，c是正整数，(a, b) = 1，2b，b < 4ac，求的关系。

第6章
第 1 节
1. 设n是正整数，证明：不定方程x2 + y2 = zn总有正整数解x，y，z。
2. 设p是奇素数，(k, p) = 1，则
，
此处是Legender符号。
3. 设素数p º 1 (mod 4)，(k, p) = 1，记
，
则2½S(k)，并且，对于任何整数t，有
，
此处是Legender符号。
4. 设p是奇素数，，则

构成模p的一个简化剩余系。
5. 在第3题的条件下，并沿用第2题的记号，有
。
即上式给出了形如4k + 1的素数的二平方和表示的具体方法。
6. 利用题5的结论，试将p = 13写成二平方和。

第 2 节
1. 若(x, y, z) = 1，则不存在整数n，使得
x2 + y2 + z2 = 4n2。
2. 设k是非负整数，证明2k不能表示三个正整数平方之和。
3. 证明：每一个正整数n必可以表示为5个立方数的代数和。
4. 证明：16k + 15型的整数至少需要15个四次方数的和表之。
5. 证明：16k×31不能表示为15个四次方数的和。

第7章
第 1 节

2. 求模14的全部原根。
3. 设m > 1，模m有原根，d是j(m)的任一个正因数，证明：在模m的简化剩余系中，恰有j(d)个指数为d的整数，并由此推出模m的简化剩余系中恰有j(j(m))个原根。
4. 设m ³ 3，g是模m的原根，x1, x2, L, xj(m)是模m的简化剩余系，证明：
(ⅰ) º -1 (mod m)；
(ⅱ) x1x2Lxj(m) º -1 (mod m)。
5. 设p = 2n + 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根。
6. 证明：
(ⅰ) 设p奇素数，则Mp = 2p - 1的素因数必为2pk + 1型；
(ⅱ) 设n ³ 0，则Fn =+ 1的素因数必为2n + 1k + 1型。
第 2 节
1. 求模29的最小正原根。
2. 分别求模293和模2×293的原根。
3. 解同余方程：x12 º 16 (mod 17)。
4. 设p和q = 4p + 1都是素数，证明：2是模q的一个原根。
5. 设m ³ 3，g1和g2都是模m的原根，则g = g1g2不是模m的原根。
6. 设p是奇素数，证明：当且仅当p - 1n时，有
1n + 2n + L + (p - 1)n º 0 (mod p)。

第8章
第 1 节
1. 补足定理1的证明。
2. 证明定理2。
3. 证明：有理数为代数整数的充要条件是这个有理数为整数。

第 2 节
1. 证明例中的结论。
2. 证明连分数

是超越数。
3. 设x是一个超越数，a是一个非零的代数数，证明：x + a，x a，都是超越数。

第 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，L，y，z，它们分别与整数00，01，L，24，25对应，又已知明文h与p分别与密文e与g对应，试求出密解公式：
P º a ¢E + b ¢ (mod 26)，
并破译下面的密文：“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（1 £ i £ 4），同时不影响其他文件的保密。
2. 利用本节中的秘密共享方案，设计一个由三方共管文件M = 3的方法，要求：只要有两方提供他们所掌握的数据，就可以求出文件M，但是，仅由任何一方的数据，不能求出文件M。（提示：取p = 5，m1 = 8，m2 = 9，m3 = 11）

第 6 节
1. 设明文P的二进制表示是P = (p1p2p3p4p5p6p7p8)2，与P对应的密文是E是E = a1p1 + a2p2 + L + a8p8，如果这里的超增背包向量(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）。

15