发布时间 : 星期五 文章4-6数论教案更新完毕开始阅读
第一章 整除理论
整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。
第一节 数的整除性
定义1 设a，b是整数，b ? 0，如果存在整数c，使得
a = bc
成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b?a；如果不存在整数c|a。 使得a = bc成立，则称a不被b整除，记为b?显然每个非零整数a都有约数 ?1，?a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。 被2整除的整数称为偶数，不被2整除的整数称为奇数。 定理1 下面的结论成立： (ⅰ) a?b ? ?a??b； (ⅱ) a?b，b?c ? a?c；
(ⅲ) b?ai，i = 1, 2, ?, k ? b?a1x1 ? a2x2 ? ? ? akxk，此处xi（i = 1, 2, ?, k）是任意的整数；
(ⅳ) 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，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。
推论 任何大于1的合数a必有一个不超过a的素约数。
2
证明 使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d1 ? a。证毕。 例1 设r是正奇数，证明：对任意的正整数n，有
|1r ? 2 r ? ? ? n r。 n ? 2?解 对于任意的正整数a，b以及正奇数k，有
ak ? bk = (a ? b)(ak ? 1 ? ak ? 2b ? ak ? 3b2 ? ? ? bk ? 1) = (a ? b)q，
r r r其中q是整数。记s = 1 ? 2 ? ? ? n，则
r r rr r r2s = 2 ? (2 ? n) ? (3 ? (n ? 1)) ? ? ? (n ? 2) = 2 ? (n ? 2)Q，
|s。 其中Q是整数。若n ? 2?s，由上式知n ? 2?2，因为n ? 2 > 2，这是不可能的，所以n ? 2?例2 设A = { d1, d2, ?, dk }是n的所有约数的集合，则
nnnB ={,,?,}
d1d2dk也是n的所有约数的集合。
解 由以下三点理由可以证得结论： (ⅰ) A和B的元素个数相同；
n(ⅱ) 若di?A，即di?n，则|n，反之亦然；
dinn?(ⅲ) 若di ? dj，则。 didj
1
例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3，? 。问：
d(1) ? d(2) ? ? ? d(1997)
是否为偶数？
nnn解 对于n的每个约数d，都有n = d?，因此，n的正约数d与是成对地出现的。只有当d =，即n
dddn2
= d时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。
d22
因为44 < 1997 < 45，所以在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的周长都相等。
解 假设这些三角形的周长都相等，记为s。则
2ns = 3(1 ? 2 ? ? ? 2n) = 3n(2n ? 1)，
即
2s = 3(2n ? 1)，
因此2?3(2n ? 1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。
例5 设整数k ? 1，证明：
kk 1kk(ⅰ) 若2 ? n < 2?，1 ? a ? n，a ? 2，则2?|a； (ⅱ) 若3 ? 2n ? 1 < 3，1 ? b ? n，2b ? 1 ? 3，则3?|2b ? 1。
kk 解 (ⅰ) 若2|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2 ，这都是不可能
k的，所以2?|a； (ⅱ) 若 3|2b-1，则存在整数q，使得2b-1= q3，显然q只可能是0，1, 或2。此时2b-1= 0，3，或2?3，
k这都是不可能的，所以3?|2b ? 1。
例6 写出不超过100的所有的素数。 解 将不超过100的正整数排列如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
按以下步骤进行：
(ⅰ) 删去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中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。
例7 证明：存在无穷多个正整数a，使得
n4 ? a（n = 1, 2, 3, ?）
都是合数。 2
kkkkk + 1
kkk解 取a = 4k，对于任意的n?N，有
n4 ? 4k4 = (n2 ? 2k2)2 ? 4n2k2 = (n2 ? 2k2 ? 2nk)(n2 ? 2k2 ? 2nk)。
因为
n2 ? 2k2 ? 2nk = (n ? k)2 ? k2 ? k2，
4
所以，对于任意的k = 2, 3, ? 以及任意的n?N，n ? 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中至少有一个偶数。如果只有一个偶数，不妨设为a1，那么2?|ai（2 ? i ? n）。此时有等式
a2 ? ? ? an = ?a1，
在上式中，左端是(n ? 1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, ?, an中至少有两个偶数，即4?n。
2
例9 若n是奇数，则8?n ? 1。 解 设n = 2k ? 1，则
n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)。
2
在k和k ? 1中有一个是偶数，所以8?n ? 1。
例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：
222
问题 d(1) ? d(2) ? ? ? d(1997)被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，A3，使得
a12 = 8A1 ? 1，a22 = 8A2 ? r，a32 = 8A3 ? s，
于是
a12 ? a22 ? a32 = 8(A1 ? A2 ? A3) ? 1 ? r ? s，
222
其中r和s是整数，而且只能取值0或4。这样a1 ? a2 ? a3被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。
综上证得所需要的结论。
4
习 题 一
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为素数）
的形式。
第二节 带余数除法
在本节中，我们要介绍带余数除法及其简单应用。
定理1(带余数除法) 设a与b是两个整数，b ? 0，则存在唯一的两个整数q和r，使得
a = bq ? r，0 ? r < |b|。 (1)
3
证明 存在性 若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|， (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，
kk则ax ? by和ab被m除的余数分别与r1x ? r2y和r1r2被m除的余数相同。特别地，a与r1被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为不全为零的整数，以y0表示集合
A = { y；y = a1x1 ? ? ? anxn，xi?Z，1 ? i ? n }
中的最小正数，则对于任何y?A，y0?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，1，2都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时
a1 ? a2 ? a3 = 3(q1 ? q2 ? q3) ? 3
可以被3整除；
(ⅱ) 若在r1, r2, ?, r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1 = r2 = r3 = r（r = 0，1或2），此时
a1 ? a2 ? a3 = 3(q1 ? q2 ? q3) ? 3r
可以被3整除。
n例4 设a0, a1, ?, an?Z，f(x) = anx ? ? ? a1x ? a0 ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则
n3?f(?1) = a0 ? a1 ? a2 ? ? ? (?1)an 。 4