tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

初等数论 第一章 整除理论


第一章

整除理论

整除性理论是初等数论的基础。 本章要介绍 带余数除法,辗转相除法,最大公约数,最小公 倍数,算术基本定理以及它们的一些应用。

第一节

数的整除性

定义 1 设 a,b 是整数,b ? 0,如果存在 整数 c,使得 a = bc 成立,则称 a 被 b 整除,a 是 b 的倍数,b 是 a 的约数(因数或除数) ,并且使用记号 b?a;如 果不存在整数 c 使得 a = bc 成立,则称 a 不被 b
| 整除,记为 b ? a。

显然每个非零整数 a 都有约数 ?1,?a,称 这四个数为 a 的平凡约数,a 的另外的约数称为 非平凡约数。 被 2 整除的整数称为偶数, 不被 2 整除的整 数称为奇数。 定理 1 下面的结论成立: (ⅰ) a?b ? ?a??b; (ⅱ) a?b,b?c ? a?c; (ⅲ) b?ai, = 1, 2, ?, k ? b?a1x1 ? a2x2 ? i

1

? ? akxk, 此处 x(i = 1, 2, ?, k) 是任意的整数; i (ⅳ) b?a ? bc?ac,此处 c 是任意的非零 整数; (ⅴ) b?a,a ? 0 ? |b| ? |a|;b?a 且|a| < |b| ? a = 0。 证明 留作习题。 定义 2 若整数 a ? 0, 并且只有约数 ?1 ?1, 和 ?a,则称 a 是素数(或质数) ;否则称 a 为合 数。 以后在本书中若无特别说明, 素数总是指正 素数。 定理 2 任何大于 1 的整数 a 都至少有一个 素约数。 证明 若 a 是素数,则定理是显然的。 若 a 不是素数, 那么它有两个以上的正的非 平凡约数,设它们是 d1, d2, ?, dk 。不妨设 d1 是 其中最小的。 d1 不是素数, 若 则存在 e1 > 1, 2 > e 1,使得 d1 = e1e2,因此,e1 和 e2 也是 a 的正的 非平凡约数。这与 d1 的最小性矛盾。所以 d1 是 素数。证毕。 推论 任何大于 1 的合数 a 必有一个不超过
a

的素约数。

证明 使用定理 2 中的记号,有 a = d1d2, 其中 d1 > 1 是最小的素约数, 所以 d12 ? a。 证毕。 例 1 设 r 是正奇数,证明:对任意的正整 数 n,有

2

| n ? 2 ? 1r ? 2 r ? ? ? n r。



对于任意的正整数 a, 以及正奇数 k, b

有 ak ? bk = (a ? b)(ak ? 1 ? ak ? 2b ? ak ? 3b2 ? ? ? bk ? 1) = (a ? b)q, 其中 q 是整数。记 s = 1r ? 2 r ? ? ? n r,则 2s = 2 ? (2 r ? n r) ? (3 r ? (n ? 1)r) ? ? ? (n r ? 2 r) = 2 ? (n ? 2)Q, 其中 Q 是整数。若 n ? 2?s,由上式知 n ? 2?2,
| 因为 n ? 2 > 2,这是不可能的,所以 n ? 2 ? s。

例 2 设 A = { d1, d2, ?, dk }是 n 的所有约数 的集合,则 B ={
n d1 , n d2 ,? , n dk

}

也是 n 的所有约数的集合。 解 由以下三点理由可以证得结论: (ⅰ) A 和 B 的元素个数相同; (ⅱ) 若 di?A,即 di?n,则 然; (ⅲ) 若 di ? dj,则
n di ? n d
j

n di

| n,反之亦



例 3 以 d(n)表示 n 的正约数的个数, 例如: 3

d(1) = 1,d(2) = 2,d(3) = 2,d(4) = 3,? 。问: d(1) ? d(2) ? ? ? d(1997) 是否为偶数? 解 对于 n 的每个约数 d,都有 n = d?
n d n d



因此,n 的正约数 d 与 当d=
n d

是成对地出现的。只有
n d

,即 n = d2 时,d 和

才是同一个数。

故当且仅当 n 是完全平方数时,d(n)是奇数。 因为 442 < 1997 < 452, 所以在 d(1), d(2), ?, d(1997)中恰有 44 个奇数,故 d(1) ? d(2) ? ? ? d(1997)是偶数。 例 4 设凸 2n 边形 M 的顶点是 A1, A2, ?, A2n,点 O 在 M 的内部,用 1, 2, ?, 2n 将 M 的 2n 条边分别编号,又将 OA1, OA2, ?, OA2n 也同 样进行编号, 若把这些编号作为相应的线段的长 度,证明:无论怎么编号,都不能使得三角形 OA1A2, OA2A3, ?, OA2nA1 的周长都相等。 解 则 2ns = 3(1 ? 2 ? ? ? 2n) = 3n(2n ? 1), 假设这些三角形的周长都相等, 记为 s。

4

即 2s = 3(2n ? 1), 因此 2?3(2n ? 1), 这是不可能的, 这个矛盾说明 这些三角形的周长不可能全都相等。 例 5 设整数 k ? 1,证明: (ⅰ) 若 2k ? n < 2k ? 1,1 ? a ? n,a ? 2k,则
| 2k ? a;

(ⅱ) 若 3k ? 2n ? 1 < 3k + 1, ? b ? n, ? 1 1 2b
| ? 3k,则 3k ? 2b ? 1。

解 (ⅰ) 若 2k|a,则存在整数 q,使得 a= q2k。显然 q 只可能是 0 或 1。此时 a= 0 或 2k ,
| 这都是不可能的,所以 2k ? a;

(ⅱ) 若 3k|2b-1, 则存在整数 q, 使得 2b-1= q3 , 显然 q 只可能是 0, 或 2。 1, 此时 2b-1= 0,
k

| 3k, 2 ? 3 , 或 这都是不可能的, 所以 3k ? 2b ? 1。
k

例 6 写出不超过 100 的所有的素数。 解 将不超过 100 的正整数排列如下: 1 8 9 10 11 18 19 20 21 28 29 30 31 38 39 40 5 32 33 34 35 36 37 22 23 24 25 26 27 12 13 14 15 16 17 2 3 4 5 6 7

41 48 49 50 51 58 59 60 61 68 69 70 71 78 79 80 81 88 89 90 91 98 99 100

42 52 62 72 82 92

43 53 63 73 83 93

44 54 64 74 84 94

45 55 65 75 85 95

46 56 66 76 86 96

47 57 67 77 87 97

按以下步骤进行: (ⅰ) 删去 1, 剩下的后面的第一个数是 2, 2 是素数; (ⅱ) 删去 2 后面的被 2 整除的数,剩下的 2 后面的第一个数是 3,3 是素数; (ⅲ) 再删去 3 后面的被 3 整除的数,剩下 的 3 后面的第一个数是 5,5 是素数; (ⅳ) 再删去 5 后面的被 5 整除的数,剩下 的 5 后面的第一个数是 7,7 是素数; ?? 照以上步骤可以依次得到素数 2, 3, 5, 7, 11, ?。 由定理 2 推论可知, 不超过 100 的合数必有 一个不超过 10 的素约数,因此在删去 7 后面被 7 整除的数以后,就得到了不超过 100 的全部素 数。

6

在例 6 中所使用的寻找素数的方法,称为 Eratosthenes 筛法。它可以用来求出不超过任何 固定整数的所有素数。在理论上这是可行的;但 在实际应用中, 这种列出素数的方法需要大量的 计算时间,是不可取的。 例 7 证明:存在无穷多个正整数 a,使得 n4 ? a(n = 1, 2, 3, ?) 都是合数。 解 取 a = 4k4,对于任意的 n?N,有 n4 ? 4k4 = (n2 ? 2k2)2 ? 4n2k2 = (n2 ? 2k2 ? 2nk)(n2 ? 2k2 ? 2nk)。 因为 n2 ? 2k2 ? 2nk = (n ? k)2 ? k2 ? k2, 所以, 对于任意的 k = 2, 3, ? 以及任意的 n?N, n4 ? a 是合数。 例 8 设 a1, a2, ?, an 是整数,且 a1 ? a2 ? ? ? an = 0,a1a2?an = n, 则 4?n。 解
| 如果 2 ? n, n, a1, a2, ?, an 都是奇数。 则

于是 a1 ? a2 ? ? ? an 是奇数个奇数之和, 不可能 等于零, 这与题设矛盾, 所以 2?n, 即在 a1, a2, ?, an 中至少有一个偶数。如果只有一个偶数,不妨

7

| 设为 a1,那么 2 ? ai(2 ? i ? n) 。此时有等式

a2 ? ? ? an = ?a1, 在上式中,左端是(n ? 1)个奇数之和,右端是偶 数,这是不可能的,因此,在 a1, a2, ?, an 中至 少有两个偶数,即 4?n。 例 9 若 n 是奇数,则 8?n2 ? 1。 解 设 n = 2k ? 1,则 n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)。 在 k 和 k ? 1 中有一个是偶数,所以 8?n2 ? 1。 例 9 的结论虽然简单, 却是很有用的。 例如, 使用例 3 中的记号,我们可以提出下面的问题: 问题 d(1)2 ? d(2)2 ? ? ? d(1997)2 被 4 除的

余数是多少? 例 10 证明:方程 a12 ? a22 ? a32 = 1999 (1) 无整数解。 解 若 a1,a2,a3 都是奇数,则存在整数 A1,A2,A3,使得 a12 = 8A1 ? 1,a22 = 8A2 ? 1,a32 = 8A3 ? 1, 于是 a12 ? a22 ? a32 = 8(A1 ? A2 ? A3) ? 3。 由于 1999 被 8 除的余数是 7,所以 a1,a2,a3 不可能都是奇数。 由式(1),a1,a2,a3 中只能有一个奇数,设 a1 为奇数,a2,a3 为偶数,则存在整数 A1,A2, 8

A3,使得 a12 = 8A1 ? 1,a22 = 8A2 ? r,a32 = 8A3 ? s, 于是 a12 ? a22 ? a32 = 8(A1 ? A2 ? A3) ? 1 ? r ? s, 其中 r 和 s 是整数,而且只能取值 0 或 4。这样 a12 ? a22 ? a32 被 8 除的余数只可能是 1 或 5,但 1999 被 8 除的余数是 7,所以这样的 a1,a2,a3 也不能使式(2)成立。 综上证得所需要的结论。

习 题 一
1. 2. np。 3. 证明:任意给定的连续 39 个自然数, 其中至少存在一个自然数, 使得这个自然数的数 字和能被 11 整除。 4. 设 p 是 n 的最小素约数, = pn1,1 > 1, n n 证明:若 p > 3
n

证明定理 1。 证明: m ? p?mn ? pq, m ? p?mq ? 若 则

,则 n1 是素数。

5. 证明:存在无穷多个自然数 n,使得 n 不能表示为 a2 ? p(a > 0 是整数,p 为素数) 的形式。

9

第二节

带余数除法

在本节中, 我们要介绍带余数除法及其简单 应用。 定理 1(带余数除法) 设 a 与 b 是两个整数, b ? 0,则存在唯一的两个整数 q 和 r,使得 a = bq ? r,0 ? r < |b|。 (1) 证明 存在性 若 b?a,a = bq,q?Z,可
| 取 r = 0。若 b ? a,考虑集合

A = { a ? kb;k?Z }, 其中 Z 表示所有整数的集合,以后,仍使用此 记号,并以 N 表示所有正整数的集合。 在集合 A 中有无限多个正整数, 设最小的正 整数是 r = a ? k0b,则必有 0 < r < |b|, (2)
| 否则就有 r ? |b|。因为 b ? a,所以 r ? |b|。于是 r

> |b|,即 a ? k0b > |b|,a ? k0b ? |b| > 0,这样,在 集合 A 中,又有正整数 a ? k0b ? |b| < r,这与 r 的最小性矛盾。所以式(2)必定成立。取 q = ? k0 知式(1)成立。存在性得证。 唯一性 假设有两对整数 q ?,r ?与 q ??,r ?? 都使得式(1)成立,即 a = q ??b ? r ?? = q ?b ? r ?,0 ? r ?, r ?? < |b|, 则 (q?? ? q ?)b = r ? ? r ??,|r ? ? r ??| < |b|,

10

(3) 因此 r ? ? r ?? = 0, ? = r ??, r 再由式(3)得出 q ? = q ??, 唯一性得证。证毕。 定义 1 称式(1)中的 q 是 a 被 b 除的商,r 是 a 被 b 除的余数。 由定理 1 可知,对于给定的整数 b,可以按 照被 b 除的余数将所有的整数分成 b 类。 在同一 类中的数被 b 除的余数相同。 这就使得许多关于 全体整数的问题可以归化为对有限个整数类的 研究。 以后在本书中,除特别声明外,在谈到带余 数除法时总是假定 b 是正整数。 例 1 设 a,b,x,y 是整数,k 和 m 是正整 数,并且 a = a1m ? r1,0 ? r1 < m, b = b1m ? r2,0 ? r2 < m, 则 ax ? by 和 ab 被 m 除的余数分别与 r1x ? r2y 和 r1r2 被 m 除的余数相同。特别地,ak 与 r1k 被 m 除的余数相同。 解 由 ax ? by = (a1m ? r1)x ? (b1m ? r2)y = (a1x ? b1y)m ? r1x ? r2y 可知,若 r1x ? r2y 被 m 除的余数是 r,即 r1x ? r2y = qm ? r,0 ? r < m, 则 ax ? by = (a1x ? b1y ? q)m ? r,0 ? r < m, 即 ax ? by 被 m 除的余数也是 r。 同样方法可以证明其余结论。 例 2 设 a1, a2, ?, an 为不全为零的整数,

11

以 y0 表示集合 A = { y;y = a1x1 ? ? ? anxn,xi?Z,1 ? i ? n } 中的最小正数, 则对于任何 y?A, 0?y; y 特别地, y0?ai,1 ? i ? n。 解 设 y0 = a1x1? ? ? ? anxn?,对任意的 y =

a1x1 ? ? ? anxn?A,由定理 1,存在 q, r0?Z,使 得 y = qy0 ? r0,0 ? r0 < y0 。 因此 r0 = y ? qy0 = a1(x1 ? qx1?) ? ? ? an(xn ? qxn?)?A。 如果 r0 ? 0,那么,因为 0 < r0 < y0,所以 r0 是 A 中比 y0 还小的正数,这与 y0 的定义矛盾。 所以 r0 = 0,即 y0?y。 显然 ai?A(1 ? i ? n) ,所以 y0 整除每个 ai (1 ? i ? n) 。 例 3 任意给出的五个整数中,必有三个数 之和被 3 整除。 解 设这五个数是 ai,i = 1, 2, 3, 4, 5,记 ai = 3qi ? ri,0 ? ri < 3,i = 1, 2, 3, 4, 5。 分别考虑以下两种情形: (ⅰ) 若在 r1, r2, ?, r5 中数 0, 2 都出现, 1, 不妨设 r1 = 0,r2 = 1,r3 = 2,此时 a1 ? a2 ? a3 = 3(q1 ? q2 ? q3) ? 3 可以被 3 整除;

12

(ⅱ) 若在 r1, r2, ?, r5 中数 0,1,2 至少有 一个不出现,这样至少有三个 ri 要取相同的值, 不妨设 r1 = r2 = r3 = r(r = 0,1 或 2) ,此时 a1 ? a2 ? a3 = 3(q1 ? q2 ? q3) ? 3r 可以被 3 整除。 例 4 设 a0, a1, ?, an?Z,f(x) = anxn ? ? ? a1x ? a0 , 已知 f(0)与 f(1)都不是 3 的倍数, 证明: 若方程 f(x) = 0 有整数解,则 3?f(?1) = a0 ? a1 ? a2 ? ? ? (?1)nan 。 对任何整数 x,都有 x = 3q ? r,r = 0,1 或 2,q?Z。 (ⅰ) 若 r = 0,即 x = 3q,q?Z,则 f(x) = f(3q) = an(3q)n ? ? ? a1(3q) ? a0 = 3Q1 ? a0 = 3Q1 ? f(0), 其中 Q1?Z,由于 f(0)不是 3 的倍数,所以 f(x) ? 0; (ⅱ) 若 r = 1,即 x = 3q ? 1,q?Z,则 f(x) = f(3q ? 1) = an(3q ? 1)n ? ? ? a1(3q ? 1) ? a0 = 3Q2 ? an ? ? ? a1 ? a0 = 3Q2 ? f(1), 其中 Q2?Z。由于 f(1)不是 3 的倍数,所以 f(x) ? 0。 因此若 f(x) = 0 有整数解 x,则必是 x = 3q ? 2 = 3q? ? 1,q ??Z,于是 0 = f(x) = f(3q ? ? 1) = an(3q ? ? 1)n ? ? ? a1(3q ? ? 1) ? a0 13 解

= 3Q3 ? a0 ? a1 ? a2 ? ? ? (? 1)nan = 3Q3 ? f(?1), 其中 Q3?Z。所以 3?f(?1) = a0 ? a1 ? a2 ? ? ? (?1)nan 。 例 5 证明: 对于任意的整数 n, = 3n5 ? f(n) 3 5n ? 7n 被 15 整除。 解 对于任意的正整数 n,记 n = 15q ? r,0 ? r < 15。 由例 1, n2 = 15Q1 ? r1,n4 = 15Q2 ? r2, 其中 r1 与 r2 分别是 r2 与 r4 被 15 除的余数。 以 R 表示 3n4 ? 5n2 ? 7 被 15 除的余数, R 则 就是 3r2 ? 5r1 ? 7 被 15 除的余数, 而且 f(n)被 15 除的余数就是 rR 被 15 除的余数,记为 R ?。 当 r = 0 时,显然 R ? = 0,即 15?3n5 ? 5n3 ? 7n。 对于 r = 1, 2, 3, ?, 14 的情形,通过计算列 出下表: r = 1, 14 6, 9 7, 8 r1 = 1 4 r2 = 1 1 R = 0 0 R?= 0 2, 13 4 1 0 0 3, 12 9 6 10 0 4, 11 1 1 0 0 5, 10 10 12 0

10 6 6 10

14

0

0

这证明了结论。 例 6 设 n 是奇数,则 16?n4 ? 4n2 ? 11。 解 我们有 n4 ? 4n2 ? 11 = (n2 ? 1)(n2 ? 5) ? 16。 由第一节例题 9,有 8?n2 ? 1,由此及 2?n2 ? 5 得到 16?(n2 ? 1)(n2 ? 5)。 例 7 证明:若 a 被 9 除的余数是 3,4,5 或 6,则方程 x3 ? y3 = a 没有整数解。 解 对任意的整数 x,y,记 x = 3q1 ? r1,y = 3q2 ? r2,0 ? r1, r2 < 3。 则存在 Q1, R1, Q2, R2?Z,使得 x3 = 9Q1 ? R1,y3 = 9Q2 ? R2 , 其中 R1 和 R2 被 9 除的余数分别与 r13 和 r23 被 9 除的余数相同,即 R1 = 0, 或 8, 2 = 0, 或 8。 1 R 1 (4) 因此 x3 ? y3 = 9(Q1 ? Q2) ? R1 ? R2 。 又由式(4)可知, 1 ? R2 被 9 除的余数只可能是 0, R 1,2,7 或 8,所以,x3 ? y3 不可能等于 a 。

习 题 二
1. 证明:12?n4 ? 2n3 ? 11n2 ? 10n,n?Z。 2. 设 3?a2 ? b2,证明:3?a 且 3?b。 3. 设 n,k 是正整数,证明:nk 与 nk + 4 的 个位数字相同。

15

4. 证明:对于任何整数 n,m,等式 n2 ? (n ? 1)2 = m2 ? 2 不可能成立。 5. 设 a 是自然数, a4 ? 3a2 ? 9 是素数还 问 是合数? 6. 证明:对于任意给定的 n 个整数,必可 以从中找出若干个作和, 使得这个和能被 n 整除。 答案

第三节

最大公约数

定义 1 整数 a1, a2, ?, ak 的公共约数称为 a1, a2, ?, ak 的公约数。 不全为零的整数 a1, a2, ?, ak 的公约数中最大的一个叫做 a1, a2, ?, ak 的最 大公约数(或最大公因数) ,记为(a1, a2, ?, ak)。 由于每个非零整数的约数的个数是有限的, 所以最大公约数是存在的,并且是正整数。 如果(a1, a2, ?, ak) = 1,则称 a1, a2, ?, ak 是 互素的(或互质的) ;如果 (ai, a j) = 1,1 ? i, j ? k,i ? j, 则称 a1, a2, ?, ak 是两两互素的 (或两两互质的) 。 显然, 1, a2, ?, ak 两两互素可以推出(a1, a2, a

16

?, ak) = 1,反之则不然,例如(2, 6, 15) = 1,但 (2, 6) = 2。 定理 1 下面的等式成立: (ⅰ) (a1, a2, ?, ak) = (|a1|, |a2|, ?, |ak|); (ⅱ) (a, 1) = 1,(a, 0) = |a|,(a, a) = |a|; (ⅲ) (a, b) = (b, a); (ⅳ) 若 p 是素数,a 是整数,则(p, a) = 1 或 p?a; (ⅴ) 若 a = bq ? r,则(a, b) = (b, r)。 证明 (ⅰ)??(ⅳ)留作习题。 (ⅴ) 由第一节定理 1 可知, 如果 d?a, d?b, 则有 d?r = a ? bq,反之,若 d?b,d?r,则 d?a = bq ? r。因此 a 与 b 的全体公约数的集合就是 b 与 r 的全体公约数的集合, 这两个集合中的最大 正数当然相等,即(a, b) = (b, r)。证毕。 由定理 1 可知,在讨论(a1, a2, ?, an)时,不 妨假设 a1, a2, ?, an 是正整数,以后我们就维持 这一假设。 定理 2 设 a1, a2, ?, ak?Z,记 A = { y;y = ?
i ?1 k

ai xi

,xi?Z,? ? i ? k }。

如果 y0 是集合 A 中最小的正数, y0 = (a1, a2, ?, 则 ak)。 17

证明

设 d 是 a1, a2, ?, ak 的一个公约数,

则 d?y0,所以 d ? y0。另一方面,由第二节例 2 知,y0 也是 a1, a2, ?, ak 的公约数。因此 y0 是 a1, a2, ?, ak 的公约数中的最大者, y0 = ( a1, a2, ?, 即 ak)。证毕。 推论 1 设 d 是 a1, a2, ?, ak 的一个公约数, 则 d?(a1, a2, ?, ak)。 这个推论对最大公约数的性质做了更深的 刻划:最大公约数不但是公约数中的最大的,而 且是所有公约数的倍数。 推论 2 ak)。 推论 3 记? = (a1, a2, ?, ak),则 (ma1, ma2, ?, mak) = |m|(a1, a2, ?,

(

a1

?

,

a2

?

,? ,

ak

?

) = 1,

特别地, (

a

,

b

) = 1。

(a, b) (a, b)

定理 3

(a1, a2, ?, ak) = 1 的充要条件是存

在整数 x1, x2, ?, xk,使得

18

a1x1 ? a2x2 ? ? ? akxk = 1。 证明 必要性 由定理 2 得到。

(1)

充分性 若式(1)成立,如果 (a1, a2, ?, ak) = d > 1, 那么由 d?a(1 ? i ? k) 推出 d?a1x1 ? a2x2 ? ? i ? akxk = 1, 这是不可能的。 所以有(a1, a2, ?, ak) = 1。证毕。 定理 4 对于任意的整数 a,b,c,下面的 结论成立: (ⅰ) 由 b?ac 及(a, b) = 1 可以推出 b?c; (ⅱ) 由 b?c, 及(a, b) = 1 可以推出 ab?c。 a?c 证明 (ⅰ) 若(a, b) = 1,由定理 2,存在 整数 x 与 y,使得 ax ? by = 1。 因此 acx ? bcy = c。 (2) 由上式及 b?ac 得到 b?c。结论(ⅰ)得证; (ⅱ) 若(a, b) = 1,则存在整数 x,y 使得式 (2)成立。由 b?c 与 a?c 得到 ab?ac,ab?bc,再 由式(2)得到 ab?c。结论(ⅱ)得证。证毕。 推论 1 若 p 是素数,则下述结论成立: (ⅰ) p?ab ? p?a 或 p?b; (ⅱ) p?a2 ? p?a。 证明 留作习题。 推论 2 若 (a, b) = 1,则(a, bc) = (a, c)。 证明 设 d 是 a 与 bc 的一个公约数, d?a, 则 d?bc,由式(2)得到,d|c, 即 d 是 a 与 c 的公 19

约数。另一方面,若 d 是 a 与 c 的公约数,则它 也是 a 与 bc 的公约数。 因此, 与 c 的公约数的 a 集合,就是 a 与 bc 的公约数的集合,所以(a, bc) = (a, c)。证毕。 推论 3 若 (a, bi) = 1,1 ? i ? n,则(a, b1b2?bn) = 1。 证明 留作习题。

定理 5 对于任意的 n 个整数 a1, a2, ?, an, 记 (a1, a2) = d2,(d2, a3) = d3,?,(dn ? 2, an ? 1) = dn ?
1,(dn ? 1,

an) = dn,

则 dn = (a1, a2, ?, an)。 由定理 2 的推论,我们有 dn = (dn ? 1, an) ? dn?an,dn?dn ? 1, dn ? 1 = (dn ? 2, an ? 1) ? dn ? 1?an ? 1,dn ? 1?dn ? 2, ? dn?an,dn?an ? 1, dn?dn ? 2, dn ? 2 = (dn ? 3, an ? 2) ? dn ? 2?an ? 2,dn ? ?dn ? 3 2 ? dn?an,dn?an ? 1, dn?an ? 2,dn?dn ? 3, ?? d2 = (a1, a2) ? dn?an,dn?an ? 1, 证明

20

?,dn?a2,dn?a1, 即 dn 是 a1, a2, ?, an 的一个公约数。 另一方面,对于 a1, a2, ?, an 的任何公约数 d,由定理 2 的推论及 d2, ?, dn 的定义,依次得 出 d?a1,d?a2 ? d?d2, d?d2,d?a3 ? d?d3, ?? d?dn ? 1,d?an ? d?dn, 因此 dn 是 a1, a2, ?, an 的公约数中的最大者,即 dn = (a1, a2, ?, an)。证毕。 例 1 证明:若 n 是正整数,则
21 n ? 4 14 n ? 3



既约分数。 解 由定理 1 得到 (21n ? 4, 14n ? 3) = (7n ? 1, 14n ? 3) = (7n ? 1, 1) = 1。 注:一般地,若(x, y) = 1,那么,对于任意 的整数 a,b,有 (x, y) = (x ?ay, y) = (x ?ay, y ? b(x ?ay)) = (x ?ay, (ab ? 1)y ? bx), 因此,
x ? ay ( ab ? 1) y ? bx

是既约分数。

21

| 例 2 证明:121 ? n2 ? 2n ? 12,n?Z。

解 由于 121 = 112, 2 ? 2n ? 12 = (n ? 1)2 ? n 11,所以,若 112?(n ? 1)2 ? 11, (3) 则 11?(n ? 1)2,因此,由定理 4 的推论 1 得到 11?n ? 1,112?(n ? 1)2。 再由式(3)得到 112?11, 这是不可能的。所以式(3)不能成立。 注:这个例题的一般形式是: 设 p 是素数,a,b 是整数,则
| pk ? (an ? b)k ? pk ? 1c,

其中 c 是不被 p 整除的任意整数,k 是任意的大 于 1 的整数。 例 3 设 a,b 是整数,且 9?a2 ? ab ? b2, (4) 则 3?(a, b)。 解 由式(4)得到 9?(a ? b)2 ? 3ab ? 3?(a ? b)2 ? 3ab ? 3?(a ? b)2 ? 3?a ? b (5) 2 ? 9?(a ? b) 。 再由式(4)得到 9?3ab ? 3?ab。 因此,由定理 4 的推论 1,得到 3?a 或 3?b。 若 3?a,由式(5)得到 3?b;若 3?b,由(5) 式也得到 3?a。因此,总有 3?a 且 3?b。 由定理 2 的推论推出 3?(a, b)。 22

| 例 4 设 a 和 b 是正整数, > 2, 2b ? 1 ? b 则

2a ? 1。 解 (ⅰ) 若 a < b,且 2b ? 1?2a ? 1。 (6) 成立,则 2b ? 1 ? 2a ? 1 ? 2b ? 2a ? 2 ? 2a(2b ? a ? 1) ? 2, 于是 a = 1,b ? a = 1, b = 2,这是不可能的, 即 所以式(6)不成立。 (ⅱ) 若 a = b,且式(6)成立,则由式(6)得 到 2a ? 1?(2a ? 1) ? 2 ? 2a ? 1?2 ? 2a ? 1 ? 2 ? 2a ? 3, 于是 b = a = 1, 这是不可能的, 所以式(6)不成立。 (ⅲ) 若 a > b,记 a = kb ? r,0 ? r < b,此 时 2kb ? 1 = (2b ? 1)(2(k ? 1)b ? 2(k ? 2)b ? ? ? 1) = (2b ? 1)Q, 其中 Q 是整数。所以 2a ? 1 = 2kb + r ? 1 = 2r(2kb ? 1 ? 1) ? 1 = 2r((2b ? 1)Q ? 1) ? 1 = (2b ? r 1)Q ? ? (2 ? 1), 其中 Q?是整数。因此 2b ? 1?2a ? 1 ? 2b ? 1?2r ? 1, 在(ⅰ)中已经证明这是不可能的,所以式(6)不能 成立。
| 综上证得 2b ? 1 ? 2a ? 1。

23

习 题 三
1. 2. 3. 4. 5y。 5. 设 a,b,c?N,c 无平方因子,a2?b2c, 证明:a?b。 6. 设 n 是正整数,求 C 12 n , C 3 n , ? , C 2 n ? 1 的 2 2n 证明定理 1 中的结论(ⅰ)—(ⅳ)。 证明定理 2 的推论 1, 推论 2 和推论 3。 证明定理 4 的推论 1 和推论 3。 设 x,y?Z,17?2x ? 3y,证明:17?9x ?

最大公约数。

第四节

最小公倍数

定义 1 整数 a1, a2, ?, ak 的公共倍数称为 a1, a2, ?, ak 的公倍数。a1, a2, ?, ak 的正公倍数 中的最小的一个叫做 a1, a2, ?, ak 的最小公倍数, 记为[a1, a2, ?, ak]。 定理 1 下面的等式成立: (ⅰ) [a, 1] = |a|,[a, a] = |a|; (ⅱ) [a, b] = [b, a]; (ⅲ) [a1, a2, ?, ak] = [|a1|, |a2| ?, |ak|];

24

(ⅳ) 若 a?b,则[a, b] = |b|。 证明 留作习题。 由定理 1 中的结论(ⅲ)可知,在讨论 a1, a2, ?, ak 的最小公倍数时,不妨假定它们都是正整 数。在本节中总是维持这一假定。 最小公倍数和最大公约数之间有一个很重 要的关系,即下面的定理。 定理 2 对任意的正整数 a,b,有 [a, b] =
ab (a, b)



证明 设 m 是 a 和 b 的一个公倍数,那么 存在整数 k1,k2,使得 m = ak1,m = bk2,因此 ak1 = bk2 。 (1) 于是
a (a, b) k1 ? b (a, b) k2



由于 ( 到

a b , ) (a, b) (a, b)

= 1,所以由第三节定理 4 得

b (a , b )

| k 1,

即 k1 ?

b (a , b )

t



其中 t 是某个整数。将上式代入式(1)得到 m=
ab (a, b)

t。

(2)

25

另一方面,对于任意的整数 t,由式(2)所确 定的 m 显然是 a 与 b 的公倍数,因此 a 与 b 的 公倍数必是式(2)中的形式, 其中 t 是整数。 t = 当 1 时,得到最小公倍数 [a, b] =
ab (a, b)



证毕。 推论 1 两个整数的任何公倍数可以被它们 的最小公倍数整除。 证明 由式(2)可得证。证毕。 这个推论说明: 两个整数的最小公倍数不但 是最小的正倍数,而且是另外的公倍数的约数。 推论 2 设 m, b 是正整数, a, 则[ma, mb] = m[a, b]。 证明 由定理 2 及第三节定理 2 的推论得到 [ma, mb] = 证毕。 定理 3 对于任意的 n 个整数 a1, a2, ?, an, 记 [a1, a2] = m2, 2, a3] = m3, [mn?2, an?1] = mn?1, [m ?, [mn?1, an] = mn, 则 [a1, a2, ?, an] = mn。 证明 我们有
m ab (ma , mb )
2

?

m ab m (a, b)

2

?

m ab (a, b)

= m[a, b]。

26

mn = [mn?1, an] ? mn?1?mn,an?mn, mn?1 = [mn?2, an?1] ? mn?2?mn?1?mn, an?mn,an?1?mn?1?mn, mn?2 = [mn?3, an?2] ? mn?3?mn?2?mn, an?mn,an?1?mn,an?2?mn, ?? m2 = [a1, a2] ? an?mn, a2?mn, ?, a1?mn, 即 mn 是 a1, a2, ?, an 的一个公倍数。 另一方面,对于 a1, a2, ?, an 的任何公倍数 m,由定理 2 的推论及 m2, ?, mn 的定义,得 m2?m,m3?m,?,mn?m。 即 mn 是 a1, a2, ?, an 最小的正的公倍数。证毕。 推论 若 m 是整数 a1, a2, ?, an 的公倍数,

则[a1, a2, ?, an]?m 。 证明 留作习题。

定理 4 整数 a1, a2, ?, an 两两互素,即 (ai, aj) = 1,1 ? i, j ? n,i ? j 的充要条件是 [a1, a2, ?, an] = a1a2?an 。

27

证明 得到

(3) 必要性 因为(a1, a2) = 1,由定理 2
a1 a 2 (a1 , a 2 )

[a1, a2] =

= a1a2 。

由(a1, a3) = (a2, a3) = 1 及第三节定理 4 推论 3 得 到 (a1a2, a3) = 1, 由此及定理 3 得到 [a1, a2, a3] = [[a1, a2], a3] = [a1a2, a3] = a1a2a3 。 如此继续下去,就得到式(3)。 充分性 用归纳法证明。当 n = 2 时,式(3) 成为[a1, a2] = a1a2。由定理 2 a1a2 = [a1, a2] =
a1 a 2 (a1 , a 2 )

? (a1, a2) = 1,

即当 n = 2 时,充分性成立。 假设充分性当 n = k 时成立,即 [a1, a2, ?, ak] = a1a2?ak ? (ai, aj) = 1,1 ? i, j ? k,i ? j。 对于整数 a1, a2, ?, ak, ak + 1,使用定理 3 中的记 号,由定理 3 可知 [a1, a2, ?, ak, ak + 1] = [mk, ak + 1]。 (4) 其中 mk = [a1, a2, ?, ak]。因此,如果

28

[a1, a2, ?, ak, ak + 1] = a1a2?akak + 1, 那么,由此及式(4)得到 [a1, a2, ?, ak, ak + 1] = [mk, ak + 1] = a1a2?akak + 1, 即
mk ( m k , a k ?1 ) m k a k ?1 ( m k , a k ?1 )

=

= a1a2?ak ,

显然 mk ? a1a2?ak,(mk, ak + 1) ? 1。所以若使上 式成立,必是 (mk, ak + 1) = 1, 并且 mk = a1a2?ak 。 由式(6)与式(5)推出 (ai, ak + 1) = 1,1 ? i ? k; (7) 由式(6)及归纳假设推出 (ai, aj) = 1,1 ? i, j ? k,i ? j 。 (8) 综合式(7)与式(8),可知当 n = k ? 1 时,充分性 成立。由归纳法证明了充分性。证毕。 定理 4 有许多应用。 例如, 如果 m1, m2, ?, mk (5)

(6)

29

是两两互素的整数, 那么, 要证明 m = m1m2?mk 整除某个整数 Q, 只需证明对于每个 i, ? i ? k, 1 都有 mi?Q。这一点在实际计算中是很有用的。 对于函数 f(x),要验证命题“m?f(n),n?Z”是 否成立,可以用第二节例 5 中的方法,验证 “m?f(r),r = 0, 1, ?, m ? 1”是否成立。这需要 做 m 次除法。 但是, 若分别验证 i?f(ri), i = 0, “m r 1, ?, mi ? 1,1 ? i ? k”是否成立,则总共需要 做 m1 ? m2 ? ? ? mk 次除法。后者的运算次数显 然少于前者。 例 1 设 a, c 是正整数, b, 证明: b, c](ab, [a, bc, ca) = abc 。 解 由定理 3 和定理 2 有 [a, b, c] = [[a, b], c] =
[ a , b ]c ([ a , b ], c )



(9) 由第三节定理 5 和定理 2 的推论, (ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b)) = ( ab ,
abc [a, b]

)?

( ab [ a , b ], abc ) [a, b]

?

ab ([ a , b ], c ) [a, b]



(10) 联合式(9)与式(10)得到所需结论。 例 2 对于任意的整数 a1, a2, ?, an 及整数 k,

30

1 ? k ? n,证明: [a1, a2, ?, an] = [[a1, ?, ak],[ak + 1, ?, an]] 解 因为[a1, a2, ?, an]是 a1, ?, ak, ak + 1, ?,

an 的公倍数,所以由定理 2 推论,推出 [a1, ?, ak]?[a1, a2, ?, an], [ak + 1, ?, an]?[a1, a2, ?, an], 再由定理 3 推论知 [[a1, ?, ak], [ak + 1, ?, an]]?[a1, a2, ?, an]。 (11) 另一方面,对于任意的 ai(1 ? i ? n) ,显然 ai?[[a1, ?, ak], [ak + 1, ?, an]], 所以由定理 3 推论可知 [a1, a2, ?, an]?[[a1, ?, ak], [ak + 1, ?, an]], 联合上式与式(11)得证。 例 3 设 a,b,c 是正整数,证明: [a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。 解 由定理 2 推论 2 及例 2,有 [a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca] = [[a2b, ab2, abc], [abc, b2c, bc2], [a2c, abc, ac2]] = [a2b, ab2, abc, abc, b2c, 2 2 2 bc , a c, abc, ac ] = [abc, a2b, a2c, b2c, b2a, 31

c2a, c2b] 以及 [a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a] = [ab, b2, ac, bc][c, a] = [ab[c, a], b2[c, a], ac[c, a], bc[c, a]] = [abc, a2b, b2c, b2a, ac2, a2c, bc2, bca] = [abc, a2b, a2c, b2c, b2a, 2 2 c a, c b], 由此得证。

习 题 四
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。

32

第五节

辗转相除法

本节要介绍一个计算最大公约数的算法— —辗转相除法, 又称 Euclid 算法。 它是数论中的 一个重要方法, 在其他数学分支中也有广泛的应 用。 定义 1 下面的一组带余数除法,称为辗转 相除法。 设 a 和 b 是整数, ? 0, b 依次做带余数除法: a = bq1 ? r1, 0 < r1 < |b|, b = r1q2 ? r2, 0 < r2 < r1 , ?? rk ? 1 = rkqk + 1 ? rk + 1,0 < rk + 1 < rk , (1) ?? rn ? 2 = rn ? 1qn ? rn, 0 < rn < rn-1 , rn ? 1 = rnqn + 1 。 由于 b 是固定的,而且 |b| > r1 > r2 > ? , 所以式(1)中只包含有限个等式。 下面,我们要对式(1)所包含的等式的个数, 即要做的带余数除法的次数进行估计。 引理 1 用下面的方式定义 Fibonacci 数列 {Fn}: F1 = F2 = 1,Fn = Fn ? 1 ? Fn ? 2,n ? 3, 那么对于任意的整数 n ? 3,有

33

Fn > ? n ? 2, 其中? =
1? 2 5

(2)



容易验证 ? 2 = ? ? 1。 当 n = 3 时,由 F3 = 2 >
1? 2 5

证明

=?

可知式(2)成立。 假设式(2)对于所有的整数 k ? n(n ? 3)成 立,即 Fk > ? k ? 2,k ? n, 则 Fn + 1 = Fn ? Fn ? 1 > ? n ? 2 ? ? n ? 3 = ? n ? 3(? ? 1) = ? n ? 3? 2 = ? n? 1, 即当 k = n ? 1 时式(2)也成立。由归纳法知式(2) 对一切 n ? 3 成立。证毕。 定理 1(Lame) 设 a, b?N,a > b,使用在式 (1)中的记号,则 n < 5log10b。 证明 在式(1)中,rn ? 1,qn + 1 ? 2,qi ? 1 (1 ? i ? n) ,因此 rn ? 1 = F2 , rn ? 1 ? 2rn ? 2 = F3 , rn ? 2 ? rn ? 1 ? rn ? F3 ? F2 = F4 , ?? b ? r1 ? r2 ? Fn + 1 ? Fn = Fn 34

, 由此及式(2)得
+2

b ? ?n = ( 即

1? 2

5

)n,

log10b ? nlog10

1? 2

5

?

1 5

n



这就是定理结论。证毕。 定理 2 使用式(1)中的记号,记 P0 = 1, 1 = q1, k = qkPk ? 1 ? Pk ? 2, P P k ? 2, Q0 = 0, 1 = 1, k = qkQk ? 1 ? Qk ? 2, Q Q k ? 2, 则 aQk ? bPk = (?1)k ? 1rk,k = 1, 2, ?, n 。 (3) 证明 当 k = 1 时,式(3)成立。 当 k = 2 时,有 Q2 = q2Q1 ? Q0 = q2,P2 = q2P1 ? P0 = q2q1 ? 1, 此时由式(1)得到 aQ2 ? bP2 = aq2 ? b(q2q1 ? 1) = (a ? bq1)q2 ? b = r1q2 ? b = ?r2, 即式(3)成立。 假设对于 k < m(1 ? m ? n)式(3)成立,由 此假设及式(1)得到 aQm ? bPm= a(qmQm ? 1 ? Qm ? 2) ? b(qmPm ? 1 ? Pm ? 2) 35

= (aQm ? 1 ? bPm ? 1)qm ? (aQm ?
2

? bPm ? 2)

= (?1)m ? 2rm ? 1qm ? (?1)m ? 3rm ? = (?1)m ? 1(rm ? 2 ? rm ? 1qm) =

2

(?1)m? 1rm , 即式(3)当 k = m 时也成立。定理由归纳法得证。 证毕。 定理 3 使用式(1)中的记号,有 rn = (a, b)。 证明 由第三节定理 1,从式(1)可见 rn = (rn ? 1, rn) = (rn ? 2, rn ? 1) = ? = (r1, r2) = (b, r1) = (a, b)。 证毕。 现在我们已经知道, 利用辗转相除法可以求 出整数 x,y,使得 ax ? by = (a, b) 。 (4) 为此所需要的除法次数是 O(log10b)。 但是如果只 需要计算(a, b)而不需要求出使式(4)成立的整数 x 与 y,则所需要的除法次数还可更少一些。 例 1 设 a 和 b 是正整数,那么只使用被 2 除的除法运算和减法运算就可以计算出(a, b)。 解 下面的四个基本事实给出了证明: (ⅰ) 若 a?b,则(a, b) = a;
| (ⅱ) 若 a = 2?a1, 2 ?
a 1,b ? 2 b 1,2 ? b 1 , |
?

? ? ? ? 1,则

(a, b) = 2? (2? ? ?a1, b1);
a ,b ? 2 b 1,2 ? b 1 , | 则(a,
?

| (ⅲ) 若 2 ?

b) = (a,

b1); 36

(



)


a ? b 2

2 ? a ,2 ? b , 则 ( a , b ) ? | |

(|

|, b ) 。

在实际计算过程中, 若再灵活运用最大公约 数的性质(例如第三节定理 4 的推论) ,则可使 得求最大公约数的过程更为简单。 例 2 用辗转相除法求(125, 17), 以及 x, y, 使得 125x ? 17y = (125, 17)。 解 做辗转相除法: 125 = 7?17 ? 6,1 = 7,1 = 6, q r 17 = 2?6 ? 5,q2 = 2,2 = 5, r 6 = 1?5 ? 1,q3 = 1,3 = 1, r 5 = 5?1, q4 = 5。 由定理 4,(125, 17) = r3 = 1。 利用定理 2 计算(n = 3) P0 = 1,P1 = 7,P2 = 2?7 ? 1 = 15,P3 = 1?15 ? 7 = 22, Q0 = 0,Q1 = 1,Q2 = 2?1 ? 0 = 2,Q3 = 1?2 ? 1 = 3, 取 x = (?1)3 ? 1Q3 = 3,y = (?1)3P3 = ?22,则 125?3 ? 17?(?22) = (125, 17) = 1。 例 3 求(12345, 678)。 解 (12345, 678) = (12345, 339) = (12006, 339) = (6003, 339) = (5664, 339) = (177, 339) = (177, 162) = (177, 81) = (96, 81) = (3, 81) = 3。 例 4 在 m 个盒子中放若干个硬币, 然后以 37

下述方式往这些盒子里继续放硬币:每一次在 n (n < m) 个盒子中各放一个硬币。 证明: 若(m, n) = 1,那么无论开始时每个盒子中有多少硬币, 经过若干次放硬币后, 总可使所有盒子含有同样 数量的硬币。 解 由于(m, n) = 1,所以存在整数 x,y,使 得 mx ? ny = 1。因此对于任意的自然数 k,有 1 ? m(?x ? kn) = n(km ? y), 这样,当 k 充分大时,总可找出正整数 x0,y0, 使得 1 ? mx0 = ny0 。 上式说明,如果放 y0 次(每次放 n 个) ,那么在 使 m 个盒子中各放 x0 个后,还多出一个硬币。 把这个硬币放入含硬币最少的盒子中 (这是可以 做到的) ,就使它与含有最多硬币的盒子所含硬 币数量之差减少 1。因此经过若干次放硬币后, 必可使所有盒子中的硬币数目相同。

习 题 五
1. 据。 2. 用辗转相除法求整数 x, 使得 1387x ? y, 162y = (1387, 162)。 3. 计算:(27090, 21672, 11352)。 4. 使用引理 1 中的记号,证明:(Fn + 1, Fn) = 1。 5. 若四个整数 2836,4582,5164,6522 说明例 1 证明中所用到的四个事实的依

38

被同一个大于 1 的整数除所得的余数相同, 且不 等于零,求除数和余数各是多少? 6. 记 Mn = 2n ? 1, 证明: 对于正整数 a, b, 有(Ma, Mb) = M(a, b)。

第六节

算术基本定理

在本节中, 我们要介绍整数与素数的一个重 要关系, 即任何大于 1 的正整数都可以表示成素 数的乘积。 引理 1 任何大于 1 的正整数 n 可以写成素 数之积,即 n = p1p2?pm, (1)

其中 pi(1 ? i ? m)是素数。 证明 当 n = 2 时,结论显然成立。 假设对于 2 ? n ? k,式(1)成立,我们来证明 式(1)对于 n = k ? 1 也成立,从而由归纳法推出 式(1)对任何大于 1 的整数 n 成立。 如果 k ? 1 是素数,式(1)显然成立。 如果 k ? 1 是合数, 则存在素数 p 与整数 d, 使得 k ? 1 = pd。 由于 2 ? d ? k, 由归纳假定知存 在素数 q1, q2, ?, ql,使得 d = q1q2?ql,从而 k ? 1 = pq1q2?ql。证毕。 定理 1(算术基本定理) 任何大于 1 的整数 n 可以唯一地表示成

39

n = p1?

1

p2 2 ? pk

?

?k



(2)

其中 p1, p2, ?, pk 是素数,1 < p2 < ? < pk, 1, ?2, p ? ?, ?k 是正整数。 证明 由引理 1,任何大于 1 的整数 n 可以 表示成式(2)的形式,因此,只需证明表示式(2) 的唯一性。 假设 pi(1 ? i ? k)与 qj(1 ? j ? l)都是素 数, p1 ? p2 ? ? ? pk,q1 ? q2 ? ? ? ql, (3) 并且 n = p1p2?pk = q1q2?ql , (4) 则由第三节定理 4 推论 1, 必有某个 qj ? j ? l) (1 , 使得 p1?qj, 所以 p1 = qj; 又有某个 pi ? i ? k) (1 , 使得 q1?pi, 所以 q1 = pi。 于是, 由式(3)可知 p1 = q1,从而由式(4)得到 p2?pk = q2?ql 。 重复上述这一过程,得到 k = l,pi = qi ,1 ? i ? k 。 证毕。 定义 1 使用定理 1 中的记号,称
? n = p1
1

p2 2 ? pk k

?

?

40

是 n 的标准分解式,其中 p(1 ? i ? k) 是素数, i p1 < p2 < ? < pk,? i(1 ? i ? k)是正整数。 推论 1 使用式(2)中的记号,有 (ⅰ) n 的正因数 d 必有形式 d=
p1 1 p 2 2 ? p k k
? ? ?

,?i?Z,0 ? ?i ? ? i,1 ? i ? k;

(ⅱ) n 的正倍数 m 必有形式 m = p 1?
1

p2

?2

? pk

?k

M,M?N,?i?N,?i ? ? i,1 ?

i ? k。 证明 留作习题。 推论 2 设正整数 a 与 b 的标准分解式是
a ? p 1 1 ? p k k q 1 1 ? q l l , b ? p 1 1 ? p k k r1
? ? ? ? ? ? ?1

? rs

?s



其中 p(1 ? i ? k) q(1 ? i ? l) r(1 ? i ? s) ,i 与 i i 是两两不相同的素数,?i,?i(1 ? i ? k) ?i(1 ? , i ? l)与?i(1 ? i ? s)都是非负整数,则 (a, b) = p 1? [a, b] =
1

? pkk
?

?

, ?i = min{?i, ?i}, ? i ? k, 1
? ? ? ?1

p 1 1 ? p k k q 1 1 ? q l l r1

? rs

?

s

, ?i =

max{?i, ?i},1 ? i ? k。 证明 留作习题。 为了方便,推论 2 常叙述为下面的形式: 推论 2 ? 设正整数 a 与 b 的标准分解式是
a ? p1 1 p 2 2 ? p k
? ? ?k

, b ? p1 1 p 2 1 ? p k

?

?

?k



其中 p1, p2, ?, pk 是互不相同的素数, i, (1 ? ? ?i

41

i ? k)都是非负整数,则
( a , b ) ? p 1 1 p 2 1 ? p k k , ? i ? min{ ? i , ? i }, 1 ? i ? k , [ a , b ] ? p 1 1 p 2 1 ? p k k , ? i ? max{ ? i , ? i }, 1 ? i ? k 。
? ? ? ? ? ?

推论 3 设 a,b,c,n 是正整数, ab = cn , b) = 1, (a, 则存在正整数 u,v,使得 a = un,b = vn,c = uv,(u, v) = 1。 证明 设 c = p 1?
1

(5)

p 21 ? p k k

?

?

,其中 p1, p2, ?,

pk 是互不相同的素数,?i(1 ? i ? k)是正整数。 又设
a ? p1 1 p 2 2 ? p k k , b ? p1 1 p 2 1 ? p k
? ? ? ? ? ?k



其中?I,?i(1 ? i ? k)都是非负整数。由式(5) 及推论 2 ?可知 min{?i, ?i} = 0,?i ? ?i = n?i,1 ? i ? k, 因此,对于每个 i(1 ? i ? k) ,等式 ?i = n?i ,?i = 0 与?i = 0,?i = n?i 有且只有一个成立。这就证明了推论。证毕。 例 1 写出 51480 的标准分解式。 解 我们有 51480 = 2?25740 = 22?12870 = 23?6435 = 23?5?1287 = 23?5?3?429 = 23?5?32?143 = 3 2 2 ?3 ?5?11?13。 例 2 设 a,b,c 是整数,证明: (ⅰ) (a, b)[a, b] = ab; 42

(ⅱ) (a, [b, c]) = [(a, b), (a, c)]。 解 为了叙述方便,不妨假定 a,b,c 是正 整数。 (ⅰ) 设
a ? p1 1 p 2 2 ? p k k , b ? p1 1 p 2 1 ? p k
? ? ? ? ? ?k



其中 p1, p2, ?, pk 是互不相同的素数,?i, (1 ? ?i i ? k)都是非负整数。由定理 1 推论 2 ?,有
( a , b ) ? p 1 1 p 2 1 ? p k k , ? i ? min{ ? i , ? i }, 1 ? i ? k , [ a , b ] ? p 1 1 p 2 1 ? p k k , ? i ? max{ ? i , ? i }, 1 ? i ? k 。
? ? ? ? ? ?

由此知 (a, b)[a, b] =
k k k

?
i ?1

pi

?i ? ? i

?

?
i ?1

pi

min{ ? i , ? i } ? max{ ? i , ? i }

?

?
i ?1

pi

?i ??i

=ab ;

(ⅱ) 设
a ?

?
i ?1

k

p i i, b ?

?

?
i ?1

k

p i i, c ?

?

?
i ?1

k

pi

?i



其中 p1, p2, ?, pk 是互不相同的素数,?i,?i,?i (1 ? i ? k)都是非负整数。由定理 1 推论 2 ?, 有
( a , [ b , c ]) ?

?
i ?1

k

p i i , [( a , b ), ( a , c )] ?

?

?
i ?1

k

pi

?i



其中,对于 1 ? i ? k,有 43

?i = min{?i, max{?i, ?i}}, ?i = max{min{?i, ?i}, min{?i, ?i}}, 不妨设?i ? ?i,则 min{?i, ?i} ? min{?i, ?i},
所以

?i = min{?i, ?i} = ?i ,
即(a, [b, c]) = [(a, b), (a, c)]。 注:利用定理 1 可以容易地处理许多像例 2 这样的问题。 例 3 证明:N
?1? 1 3 ? 1 5 ?? ? 1 2n ? 1

(n ?

2)不是整数。 解 设 3k ? 2n ? 1 < 3k + 1。 对于任意的 1 ? i ? n,2i ? 1 ? 3k,记 2i ? 1 = 3 ? Qi,Qi?Z,
i

由第一节例 5, ?i ? k ? 1。 知 因为 3k ? 1Q1Q2?Q2n 所以, 如果 ? 1 是整数, 使得 3k ? 1Q1Q2?Q2n ? 1N = Q ? 3k ? 1Q1Q2?Q2n ?1
1 3
k

N 是整数, 则存在整数 Q,



| 由于 3 ? Q1Q2?Q2n?1,所以上式右端不是整数,

这个矛盾说明 N 不能是整数。

44

习 题 六
1. 2. 3. 4. 证明定理 1 的推论 1。 证明定理 1 的推论 2。 写出 22345680 的标准分解式。 证明:在 1, 2, ?, 2n 中任取 n ? 1 数,

其中至少有一个能被另一个整除。 5. 证明: ? 1
1 2 ?? ? 1 n

(n ? 2) 不是整数。

6. 设 a,b 是正整数,证明:存在 a1,a2, b1,b2,使得 a = a1a2,b = b1b2,(a2, b2) = 1, 并且[a, b] = a2b2。

第七节

函数[x]与{x}

本节中要介绍函数[x], 它在许多数学问题中 有广泛的应用。 定义 1 设 x 是实数,以[x]表示不超过 x 的 最大整数, 称它为 x 的整数部分, 又称{x} = x ? [x] 为 x 的小数部分。 定理 1 设 x 与 y 是实数,则 (ⅰ) x ? y ? [x] ? [y]; (ⅱ) 若 m 是整数,则[m ? x] = m ? [x]; (ⅲ) 若 0 ? x < 1,则[x] = 0; ( ⅳ ) [x ? y] =

45

? [x] ? [ y] ? ?[ x ] ? [ y ] ? 1

若 { x} ? { y } ? 1 若 { x} ? { y } ? 1 ? ? [x] ?? [x] ? 1 ? 0



(ⅴ) [?x] = ?

若 x?Z 若 x?Z 若 x?Z 若 x?Z



(ⅵ) {?x} = ? 证明

?1 ? { x }



留作习题。

定理 2 设 a 与 b 是正整数, 则在 1, 2, ?, a 中能被 b 整除的整数有 [ ] 个。
b a

证明

能被 b 整除的正整数是 b, 2b, 3b, ?,

因此,若数 1, 2, ?, a 中能被 b 整除的整数有 k 个,则 kb ? a < (k ? 1)b ? k ?
a b

< k ? 1 ? k =[ ] 。
b

a

证毕。 由定理 2 我们看到,若 b 是正整数,那么对 于任意的整数 a,有
a ? b[ a b

] ? b{ } ,
b

a

即在带余数除法 a = bq ? r,0 ? r < b 中有 q
?[ a b

],r

? b{

a b

}。

46

? 定理 3 设 n 是正整数, = p 1 n!

1

p2 2 ? pk k

?

?



n!的标准分解式,则

?i = ? [
r ?1

?

n pi
r

]。

(1)

证明 对于任意固定的素数 p,以 p(k)表示 在 k 的标准分解式中的 p 的指数,则 p(n!) = p(1) ? p(2) ? ? ? p(n)。 以 nj 表示 p(1), p(2), ?, p(n)中等于 j 的个数,那 么 p(n!) = 1?n1 ? 2?n2 ? 3?n3 ? ? , (2) 显然,nj 就是在 1, 2, ?, n 中满足 pj?a 并且
| pj + 1 ? a 的整数 a 的个数,所以,由定理 2 有

nj = [

n p
j

]?[
p

n
j ?1

]。

将上式代入式(2),得到
p ( n ! ) ? 1([
?

n p

]?[
n

n p
2

])

? 2 ([

n p
2

]?[

n p
3

])

? 3 ([

n p
3

]?[

n p
4

])

??

?

?[
r ?1

p

r

]。

47

即式(1)成立。证毕。 推论 设 n 是正整数,则 n! = ?
p?n
?

?[

n p
r

]

p

r ?1



其中 ? 表示对不超过 n 的所有素数 p 求积。
p?n

定理4 设 n 是正整数,1 ? k ? n ? 1,则
Cn ?
k

n! k ! ( n ? k )!

?N。 (3)

若 n 是素数,则 n? C k ,1 ? k ? n ? 1。 n 证明 由定理 3,对于任意的素数 p,整数 n!,k!与(n ? k)!的标准分解式中所含的 p 的指数 分别是

?[
r ?1

?

n p
r

], ? [
r ?1

?

k p
r

]



?[
r ?1

?

n ? k p
r

]。

利用定理 1 可知

?[
r ?1

?

n p
r

]? ?[
r ?1

?

k p
r

]? ? [
r ?1

?

n ? k p
r

],

因此 C k 是整数。 n 若 n 是素数,则对于 1 ? k ? n ? 1,有 (n, k!) = 1,(n, (n ? k)!) = 1 ? (n, k!(n ? k)!) = 1, 由此及

48

Cn ?

k

n ? ( n ? 1 )! k ! ( n ? k )!

?N,

推出 k!(n ? k)!?(n ? 1)!,从而 n? C k 。证毕。 n 例 1 求最大的正整数 k,使得 10k?199!。 解 由定理 3,199!的标准分解式中所含的 5 的幂指数是

[

199 5

]?[

199 5
2

]?[

199 5
3

] ? ? = 47,

所以,所求的最大整数是 k = 47。 例 2 设 x 与 y 是实数,则 [2x] ? [2y] ? [x] ? [x ? y] ? [y]。 (4) 解 设 x = [x] ? ?,0 ? ? < 1,y = [y] ? ?,0 ? ? < 1,则 [x] ? [x ? y] ? [y] = 2[x] ? 2[y] ? [? ? ?], (5) [2x] ? [2y] = 2[x] ? 2[y] ? [2?] ? [2?]。 (6) 如果[? ? ?] = 0, 那么显然有[? ? ?] ? [2?] ? [2?]; 如果[? ? ?] = 1,那么?与?中至少有一个不 小于
1 2

,于是

[2?] ? [2?] ? 1 = [? ? ?]。 因此无论[? ? ?] = 0 或 1,都有[? ? ?] ? [2?] ? [2?],由此及式(5)和式(6)可以推出式(4)。 例 3 设 n 是正整数,则 49

[ n ?

n ? 1] ? [ 4n ? 2 ]

。 (7)


[ n ?

首先,我们有
n ? 1] ? ? n ? n ?1 ? 2n ? 1 ? 2 n ( n ? 1)

2n ? 1 ? 2n ? 1 ?

4n ? 2 ,

所以
[ n ? n ? 1] ? [ 4n ? 2 ] 。

若上式中的等号不成立,即
[ n ? n ? 1] ? [ 4n ? 2 ] ,

(8) 则存在整数 a,使得
[ n ? n ? 1] ? a ? [ 4n ? 2 ] ,

因此
2n ? 1 ? 2 2 n
2

n ( n ? 1) ? a
2

2

? 4n ? 2 ,

? n ? a

? 2n ? 1 ? 2n ? 1,

(2n ? 1)2 ? 1< (a2 ? 2n ? 1)2 ? (2n ? 1)2, 所以 a2 ? 2n ? 1 = 2n ? 1 ? a2 = 4n ? 2。 (9)
| 但是,无论 2?a 或 2 ? a,式(9)都不能成立,这

个矛盾说明式(8)不能成立,即式(7)成立。 例 4 设 x 是正数,n 是正整数,则 50

[x] ? [ x ?

1 n

] ? [x

?

2 n

]??
i

? [x ? ?? ?

n ?1 n

] = [nx]。

解 1,则

设 x = [x] ? ?,

i?1 n

, ?i?n? 0
n ?1 n

n

[x] ? [ x ?

1 n

] ? [x

?

2 n

]??

? [x ?

]

= n[x] ? i = n[x] ? [n?] = [n([x] ?

?)] = [nx]。
例 5 求[ ( 解
(
3 ? 2)
2 1992

]的个位数。 得
1 9 9 2

由(
3 ?

3 ?

2)
1 9 9 2

?5? 2 6

2)

?(

3 ?

2)

= ( 5 ? 2 6 ) 996 ? ( 5 ? 2 6 ) 996 =
2 (5
996

? C 996 ? 5
2

994

2 ?6 ?? ? 2
2

996

6

498

)

= 10A ? 2997?6498 = 10A ? 2?24498= 10A ? 2(25 ? 1)498 = 10B ? 2 , (10) 其中 A 和 B 都是整数。由于 0 < 5 ? 2 以,由式(10)可知[ (
3 ? 2)
1996

6

< 1,所

]的个位数是 1。
B

注: 一般地, 如果 A, B?N, 2 > B,A ? A

51

< 1,则由
(A ? B)
k

? (A ? B)

B)
k

k

? 2( A

k

? Ck A

2

k ?2

B ? ?)

可以求出[ ( A ?

]。
1 x ? 1 y ? 1 ,证

例 6 设 x 和 y 是正无理数, 明:数列

[x], [2x], ?, [kx], ? 与 [y], [2y], ?, [my], ? (11) 联合构成了整个正整数集合,而且,两个数列中 的数互不相同。 解 显然 x > 1,y > 1,并且 x ? y。因此, 在数列(11)中至多有一个数等于给定的正整数 n, 否则存在正整数 k 与 m,使得 n = [kx] = [my]。 因为 x 与 y 都是无理数,所以我们有 n < kx < n ? 1,n < my < n ? 1,
k n ?1 ? 1 x ? 1 x ? k n ? 1 y , m n ?1 ?1? ? 1 y k ? m n ? m n , ,

k ? m n ?1

n < k ? m < n ? 1, 这是不可能的。 下面证明,对于任意给定的正整数 n,总可 找到某个正整数 k,使得 n 等于[kx]或者[ky]。假 设不然,则存在 p, q?N,使得 52

[px] < n < [(p ? 1)x],[qy] < n < [(q ? 1)y]。 于是(因为 x 和 y 是无理数) , px < n < n ? 1 ? [(p ? 1)x] < (p ? 1)x, qy < n < n ? 1 ? [(q ? 1)y] < (q ? 1)y,
p ? q n ? 1 x ? 1 y ?1? p ? q ? 2 n ?1



p ? q < n < n ? 1 < p ? q ? 2, 这是不可能的。

习 题 七
1. 2. 3. 证明定理 1。 求使 12347!被 35k 整除的最大的 k 值。 设 n 是正整数,x 是实数,证明:
r ?1 r

?[
r ?1

?

n? 2 2

] = n。

设 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 的二进制表示的位数码之 和。 4.

53

第八节





在第六节中我们已经证明了: 每个正整数可 以表示成素数幂的乘积。这就引出了一个问题: 素数是否有无穷多个?如果有无穷多个,那么, 作为无穷大量, 素数个数具有怎样的性状?这是 数论研究中的一个中心课题。 本节要对这一问题 作初步的研究。 定义 1 对于正实数 x,以?(x)表示不超过 x 的素数个数。 例如,?(15) = 6,?(10.4) = 4,?(50) = 15。 定理 1 素数有无限多个。 证明 我们给出三个证明方法。 证法Ⅰ 假设只有 k 个素数, 设它们是 p1, p2, ?, pk 。记 N = p1p2?pk ? 1。 由第一节定理 2 可知,N 有素因数 p,我们要说 明 p ? pi ,1 ? i ? k,从而得出矛盾。 事实上, 若有某个 i, ? i ? k, 1 使得 p = pi , 则由 p?N = p1p2?pk ? 1 推出 p?1,这是不可能的。因此在 p1, p2, ?, pk 之外又有一个素数 p,这与假设是矛盾的。所以 素数不可能是有限个。 证法Ⅱ 我们证明整数

54

2 ? 1, 2

2

? 1, 2

2

2

? 1, ? , 2

2

n

? 1, ?

是两两互素的, 从而由第六节引理 1 可知素数有 无限多个。 事实上,若 m 和 n 是整数,m > n ? 0,则
2
2
m

? 1 ? (2 ? (2 ?? ? (2

2

m ?1

? 1)( 2 ? 1)( 2

2

m ?1

? 1) ? 1)( 2
2
m?2

2

m ?1

2

m?2

? 1)

2

mn ? 1

? 1)( 2 ? 1) ,

2

m?2

? 1) ? ( 2

2

n

? 1)( 2

2

n

? 1)

? Q (2

2

n

此处 Q 是整数。因此
2
2
m

? 1 ? Q (2

2

n

? 1) ? 2 ,


(2
2
m

? 1, 2

2

n

? 1) ? ( 2 , 2

2

n

? 1) ? 1 。

证法Ⅲ

假设只有有限个素数 p1, p2, ?, pk 。

由第六节定理 1,每个正整数可以写成
? n = p1
1

p2 2 ? pk k

?

?

,?i ? 1,1 ? i ? k。

由于

(1 ?

1 p

) ?1

?

?
? ?0

?

1 p
?



所以,对于任何正整数 N,有

55

1?

1 2

?

1 3

?? ?

1 N

? (1 ?

1 p1

) ? 1 (1 ?

1 p2

) ? 1 ? (1 ?

1 pk

) ?1

。 当 N?? 时, 上式左端是一个无穷大量, 右端是 有限的,这个矛盾说明素数不能是有限多个。证 毕。 注 1:形如 2 2
n

? 1 (n

= 0, 1, 2, ?)的数称

为 Fermat 数。Fermat 曾经猜测它们都是素数。 这是错误的,因为尽管 F0,F1,F2,F3,F4 都是 素数,F5 = 2 2
5

? 1 ? 641 ? 6700417

却是合数。

注 2:将全体素数按大小顺序排列为 p1 = 2,p2 = 3,p3 = 5,p4,?,pn,?, 那么由第一个证明方法可以看出 pn + 1 ? p1p2?pn ? 1,n ? 1。 定理 2 对于 n ? 1, (ⅰ) ?(n) ?
1 2

log2n;

(ⅱ) pn ? 22n。 证明 (ⅰ) 设 n 是大于 1 的正整数。由算 术基本定理,对于任意的整数 k,1 ? k ? n,都 有整数 a 和 b,使得 k = a2b,其中整数 b 不能被 任何大于 1 的整数的平方整除。现在,我们来看 使得 k = a2b,1 ? k ? n (1) 56

即 1 ? a2b ? n 成立的整数 a, 有多少对。 b 首先, 整数 a 的个数 ?
n

;其次,由于 b ? n 并且不

含有平方因数,所以,整数 b 的因数只可能是不 超过 n 的不同的素数的乘积,因此,整数 b 的个 数 ? 2?(n)。这样,使得式(1)成立的整数 a 和 b 至多是
1 2

n

2?(n) 对,所以,n ?

n

2?(n),即?(n) ?

log2n。 (ⅱ) 以 pm 表示第 m 个素数,在结论(ⅰ)

中取 n = pm,我们得到 m ?

1 2

log2pm,由此即可

得到结论(ⅱ)。证毕。 注:定理 2 对于无穷大量?(x)的下界估计是 相当粗糙的。下面的定理是已经知道的(由于其 证明较繁,故本书中不予证明) 。 定理 3(素数定理) 我们有

?(x) ?

x log x

, (x??) ,

此处 logx 是以 e 为底的 x 的对数。 推论 以 pn 表示第 n 个素数,则 pn ? nlogn(n??) 。 证明 由定理 3,当 n?? 时,有 n? 因此 nlogpn ? pn, 57
pn log p n



(2)

logn ? loglogpn ? logpn, logn ? logpn。 由上式与式(2)得 pn ? nlogn(n??) 。证毕。 n 例 1 若 a > 1,a ? 1 是素数,则 a = 2, 并且 n 是素数。 解 若 a > 2,则由 an ? 1 = (a ? 1)(an ? 1 ? an ? 2 ? ? ? 1) 可知 a n ? 1 是合数。所以 a = 2。 若 n 是合数,则 n = xy,x > 1,y > 1,于是 由 2xy ? 1 = (2x ? 1)(2x(y ? 1) ? 2x(y ? 2) ? ? ? 1) 以及 2x ? 1 > 1 可知 2n ? 1 是合数,所以 2n ? 1 是素数时,n 必是素数。 注:若 n 是素数,则称 2n ? 1 是 Mersenne 数。 例 2 形如 4n ? 3 的素数有无限多个。 解 若不然, 假设只有 k 个形如 4n ? 3 的素 数 p1, p2, ?, pk。记 N = 4p1p?pk – 1。 由第六节引理 1, 正整数 N 可以写成若干个 素数之积。我们指出,这些素因数中至少有一个 是 4n ? 3 形式。 否则, 若它们都是 4n ? 1 的形式, 则 N 也是 4n ? 1 的形式,这与 N 的定义矛盾。 以 p 表示这个素因数,则 p ? pi,1 ? i ? k。否则 若有某个 i,1 ? i ? k,使得 p = pi,则由 p?N 推 出 p?1,这是不可能的。因此在 p1, p2, ?, pk 之 外又存在一个形如 4n ? 3 的素数 p,这与原假设 58

矛盾,所以形如 4n ? 3 的素数有无限多个。 例 3 设 f(x) = akxk ? ak ? 1xk ? 1 ? ? ? a0 是整 系数多项式,那么,存在无穷多个正整数 n,使 得 f(n)是合数。 解 不妨假定 ak > 0。于是 f(x)? ??(x? ??) ,因此,存在正整数 N,使得当 n > N 时, 有 f(n) > 1。取整数 x > N,记 y = f(x) = akxk ? ak ? 1xk ? 1 ? ? ? a0, 又设 r 是任意的正整数,n = ry ? x,则 f(n) = f(ry ? x) = ak(ry ? x)k ? ak ? 1(ry ? x)k ? 1 ? ? ? a0 = yQ ? f(x) = y(Q ? 1) 是合数。

习 题 八
1. 幂。 2. 证明:若 2n ? 1 是素数,则 n 是素数。 3. 证明:形如 6n ? 5 的素数有无限多个。 4.
| 设 d 是正整数,6 ? d,证明:在以 d 为

证明:若 2n ? 1 是素数,则 n 是 2 的乘

公差的等差数列中, 连续三项都是素数的情况最 多发生一次。 5. 证明:对于任意给定的正整数 n,必存 在连续的 n 个自然数,使得它们都是合数。

59

6.

证明:级数 ?
n ?1

?

1 pn

发散,此处使用了定

理 1 注 2 中的记号。

60


推荐相关:

初等数论:数的整除性_图文.pdf

初等数论:数的整除性 - 《初等数论第一章 整数的可除性 第一章 整除理论 整除性理论是初等数论的基础。 本章要介绍带余数除法,辗转相除法,最大公约数, ...


初等数论1整除_图文.pdf

初等数论1整除 - 《初等数论(闵嗣鹤、严士健)》第三版... 第一章 整数的可除性整除理论初等数论的基础,本章要介绍 带余数除法,辗转相除法,最大公约数,最小...


初等数论第一章1_图文.ppt

初等数论第一章1 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


初等数论 第一章 整除1-4_图文.ppt

初等数论 第一章 整除1-4 - 《初等数论》 教师:何艳 2015-4-28 11:11 数论的基本内容 按照研究方法的不同,数论可分为 初等数论 解析数论 代数数论 几何...


初等数论第一章3_图文.ppt

初等数论第一章3 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


§2初等数论--整除_图文.ppt

可是这也说明了最难的数论问题,适合于任 何人去研究。 初等数论最基础的理论在于整除,由它可以演化出许 多数论定理。 第一章 整数的可除性整除理论是初等...


初等数论§1整除_图文.ppt

初等数论§1整除 - 第一章 整数的可除性 整除理论初等数论的基础,本章要介


初等数论第一章4_图文.ppt

初等数论第一章4 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


初等数论第一章7_图文.ppt

初等数论第一章7 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


《数论》第一章补充例题.doc

《数论》第一章补充例题 - 《数论》第一章补充例题 整除理论初等数论的基础.


初等数论第一章2_图文.ppt

初等数论第一章2 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


初等数论.doc

初等数论 - 第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法,


§2初等数论--整除_图文.ppt

§2初等数论--整除 - 第一章 整数的可除性 整除理论初等数论的基础,本章


第一节 数的整除性.doc

第一节 数的整除性 - 初等数论 术基本定理以及它们的一些应用。 第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法,辗转相除法,最大公约数,...


初等数论第一章5_图文.ppt

初等数论第一章5 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


初等数论第一章6_图文.ppt

初等数论第一章6 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 要介绍带余数除法,辗转相除法,最 大公约数,最小公倍数,...


_初等数论_教学初探_图文.pdf

包括整除性、 不 定方程、 同余理论、 连分数、 素数分布以及数论函数 等内容...成了初等数论的重要部分, 文 第一章研究某些整数间的整除性 , 第三章就研究...


初等数论第一章引言_图文.ppt

初等数论第一章引言 - 初等数论 Number Theory 第一章 整除理论 ? 整除性理论是初等数论的基础。本章 整除性理论是初等数论的基础。 要介绍自然数与整数,带余数...


《数论》第一章补充例题.pdf

《数论》第一章补充例题 - 整除理论补充例题? 彭道意? September 27, 2013 整除性理论是初等数论的基础. 本章要介绍带余数除法, 辗转相除法, 最大公约数, 最...


第五节初等数论中的几个重要定理.doc

3页 免费 初等数论 第一章 整除理论... 61页 1财富值喜欢此文档的还喜欢 ...第五节基础知识 初等数论中的几个重要定理 定义(欧拉(Euler)函数)一组数 x1 ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com