初等数论习题集

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