《初等数论》习题集
第1章
第 1 节
1. 证明定理1。
2. 证明：若m ? p?mn ? pq，则m ? p?mq ? np。
3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。
4. 设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >3n，则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。
32n?16. 设n是正整数，求C12n,C2n,?,C2n的最大公约数。
第 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是正整数，证明：
[a,b,c]2(a,b,c)2?。
[a,b][b,c][c,a](a,b)(b,c)(c,a) 6. 设k是正奇数，证明：1 ? 2 ? ? ? 9?1k ? 2k ? ? ? 9k。
第 5 节
1. 说明例1证明中所用到的四个事实的依据。
2. 用辗转相除法求整数x，y，使得1387x ? 162y = (1387, 162)。
1
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, ?, 2n中任取n ? 1数，其中至少有一个能被另一个整除。
115. 证明：1????（n ? 2）不是整数。
2n6. 设a，b是正整数，证明：存在a1，a2，b1，b2，使得
a = a1a2，b = b1b2，(a2, b2) = 1，
并且[a, b] = a2b2。
第 7 节
1. 证明定理1。
2. 求使12347!被35k整除的最大的k值。
n?2r?13. 设n是正整数，x是实数，证明：?[]= n。
2rr?1?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 是正整数，6?|d，证明：在以d为公差的等差数列中，连续三项都是素数的情况最多发生一次。
5. 证明：对于任意给定的正整数n，必存在连续的n个自然数，使得它们都是合数。
?16. 证明：级数?发散，此处使用了定理1注2中的记号。
pn?1n
第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?62??427，求?与?。
第 2 节
1. 证明定理1。
2. 证明：若2p ? 1是奇素数，则
(p!)2 ? (?1)p ? 0 (mod 2p ? 1)。 3. 证明：若p是奇素数，N = 1 ? 2 ? ? ? ( p ? 1)，则
(p ? 1)! ? p ? 1 (mod N)。
4. 证明Wilson定理的逆定理：若n > 1，并且
(n ? 1)! ? ?1 (mod n)，
则n是素数。
5. 设m是整数，4?m，{a1, a2, ?, am}与{b1, b2, ?, bm}是模m的两个完全剩余系，证明：{a1b1, a2b2, ?, ambm}不是模m的完全剩余系。
6. 设m1, m2, ?,mn是两两互素的正整数，?i（1 ? i ? n）是整数，并且
?i ? 1 (mod mi)， 1 ? i ? n， ?i ? 0 (mod mj)，i ? j，1 ? i, j ? n。
证明：当bi通过模mi（1 ? i ? n）的完全剩余系时， b1?1 ? b2?2 ? ? ? bn?n
通过模m = m1m2?mn的完全剩余系。
第 3 节
1. 证明定理1。
2. 设m1, m2, ?, mn是两两互素的正整数，xi分别通过模mi的简化剩余系（1 ? i ? n），
mm = m1m2?mn，Mi =，则
miM1x1 ? M2x2 ? ? ? Mnxn
通过模m的简化剩余系。
3. 设m > 1，(a, m) = 1，x1, x2, ?, x?(m)是模m的简化剩余系，证明：
?(m)i?1?{mi}?2?(m)。
ax1其中{x}表示x的小数部分。
4. 设m与n是正整数，证明：
?(mn)?((m, n)) = (m, n)?(m)?(n)。
5. 设a，b是任意给定的正整数，证明：存在无穷多对正整数m与n，使得
a?(m) = b?(n)。
6. 设n是正整数，证明：
3
(ⅰ) ?(n) >
1n； 2(ⅱ) 若n是合数，则?(n) ? 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相似的结论？
第4章
第 1 节
17写成三个既约分数之和，它们的分母分别是3，5和7。 1052. 求方程x1 ? 2x2 ? 3x3 = 41的所有正整数解。 3. 求解不定方程组：
1. 将
?x1?2x2?3x3?7。 ?2x?5x?20x?1123?14. 甲班有学生7人，乙班有学生11人，现有100支铅笔分给这两个班，要使甲班的
学生分到相同数量的铅笔，乙班学生也分到相同数量的铅笔，问应怎样分法？
5. 证明：二元一次不定方程ax ? by = n，a > 0，b > 0，(a, b) = 1的非负整数解的个数为[n]或[n]? 1。 abab(a?1)(b?1)个整数
2 6. 设a与b是正整数，(a, b) = 1，证明：1, 2, ?, 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 节
4
1. 求方程x2 ? xy ? 6 = 0的整数解。 ?x?y?z?02. 求方程组?3的整数解。 33x?y?z??18?3. 求方程2x ? 3y = 1的正整数解。 1114. 求方程??的正整数解。
xyz5. 设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. 解同余方程组：
?3x?5y?38(mod47)。 ?x?y?10(mod47)?4. 设p是素数，0 < a < p，证明：
x?b(?1)a?1(p?1)(p?2)???(p?a?1)(mod p)。
a!是同余方程ax ? b (mod p)的解。
5. 证明：同余方程a1x1 ? a2x2 ? ? ? anxn ? b (mod m)有解的充要条件是
(a1, a2, ?, an, m) = d?b。
若有解，则恰有d?mn ?1个解，mod m。
6. 解同余方程：2x ? 7y ? 5 (mod 12)。
第 2 节
?x?b1(mod5)??x?b2(mod6)1. 解同余方程组：?
x?b(mod7)3???x?b4(mod11)。?x?8(mod15)?2. 解同余方程组：?x?5(mod8)
?x?13(mod25)。?3. 有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知这队士兵不超过170人，问这队士兵有几人？
5
4. 求一个最小的自然数n，使得它的
111是一个平方数，它的是一个立方数，它的是253一个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)?(x ? p ? 1) (mod p)； (ⅱ) (p ? 1)! ? ? 1 (mod p)。
6. 设p ? 3是素数，证明：(x ? 1)(x ? 2)?(x ? p ? 1)的展开式中除首项及常数项外，所有的系数都是p的倍数。
第 5 节
1. 同余方程x2 ? 3 (mod 13)有多少个解？
2. 求出模23的所有的二次剩余和二次非剩余。
3. 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。
n4. 设素数 p ? 3 (mod 4)，()= 1，证明x ? ?npp?14(mod p)是同余方程
x2 ? n (mod p)
的解。
5. 设p是奇素数，(n, p) = 1，?是正整数，证明同余方程
6
x2 ? n (mod p?)
有解的充要条件是(np)= 1。 p?16. 设p是奇素数，证明：模p的所有二次剩余的乘积与(?1)2对模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，证明：(dp)= 1。
4. 设p，q是两个不同的奇素数，且p = q ? 4a，证明：(ap)?(aq)。 5. 设a > 0，b > 0，b为奇数，证明：
?(a?a当a?0，1(mod4)2a?b)(??b)
?a??(b)当a?2，3(mod4)。 6. 设a，b，c是正整数，(a, b) = 1，2?|b，b < 4ac，求(a4ac?b)与(ab)的关系。
第 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
第7章
第 1 节
2. 求模14的全部原根。
3. 设m > 1，模m有原根，d是?(m)的任一个正因数，证明：在模m的简化剩余系中，恰有?(d)个指数为d的整数，并由此推出模m的简化剩余系中恰有?(?(m))个原根。
4. 设m ? 3，g是模m的原根，x1, x2, ?, x?(m)是模m的简化剩余系，证明：
?(m)(ⅰ) g2? ?1 (mod m)；
(ⅱ) x1x2?x?(m) ? ?1 (mod m)。
5. 设p = 2n ? 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根。 6. 证明：
(ⅰ) 设p奇素数，则Mp = 2p ? 1的素因数必为2pk ? 1型； (ⅱ) 设n ? 0，则Fn =22? 1的素因数必为2n + 1k ? 1型。
n第 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 ? 1?|n时，有
1n ? 2n ? ? ? (p ? 1)n ? 0 (mod p)。
第9章
第 1 节
1. 利用例1中的加密方法，将“ICOMETODAY”加密。
2. 已知字母a，b，?，y，z，它们分别与整数00，01，?，24，25对应，又已知明文h与p分别与密文e与g对应，试求出密解公式：
P ? a ?E ? b ? (mod 26)，
并破译下面的密文：“IRQXREFRXLGXEPQVEP”。
第 2 节
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的传送和认证过程。
8