第九节 自然数的性质

教学目的：1、掌握第一、第二数学归纳法；

2、掌握最小自然数原理；

3、掌握并会应用抽屉原理.

教学重点：应用最小自然数原理以及抽屉原理.

教学过程

1、归纳原理  设是的一个子集，满足条件：

(1) ; (2) 如果，则. 那么.

2、数学归纳法  设是关于自然数的一种性质或命题. 如果 (1) 当时，成立；

(2) 由成立必可推出成立，

那么，对所有自然数都成立.

   证明：设使成立的所有自然数所组成的集合是，则是的一个子集. 由条件(1) 知;由条件 (2)知若，则，那么.

    3、最小自然数原理 设是的一个非空子集. 那么，必有，使得对所有，都有，即是中的最小自然数.

4、第二数学归纳法设是关于自然数的一种性质或命题. 如果

(1) 当时，成立；

(2) 设，若对所有自然数，成立，必可推出成立，那么，对所有自然数都成立.

5、抽屉原理 把件东西任意放入只抽屉里，那么至少有一个抽屉里有两件东西.

把件东西放入个抽屉里，那么至少有一个抽屉里至少有+1件东西.

无穷件东西，把它们放在有限多个抽屉里，那么至少有一个抽屉里含无穷件东西.

例1、证明：若表示第个素数，则.

证明：略.

例2、在边长为1的正方形内任意放置5个点，试证：其中必有两个点，它们之间的距离不大于.

                    

证明：将边长为1的正方形划分成如图所示的四个边长为的小正方形，则每个小正方形中任意两点间的距离不大于，据抽屉原理：5个点放入四个正方形中，其中至少有一个正方形中至少有2个点，则这两个点间的距离不大于.

例3、求证：任给五个整数，必能从中选出三个，使得它们的和能被3整除.

证明：因为任意一个整数被3除的余数只能是0、1、2，若任给的5个整数被3除的余数中0、1、2都出现，则余数为0、1、2的三个整数之和能被3整除.若5个数被3除的余数只出现0、1、2中的两个，则据抽屉原理知：必有3个整数的余数相同，而余数相同的3个数之和能被3整除.故任给五个整数，必能从中选出三个，使得它们的和能被3整除.

例4、证明：在全世界所有人中任选六个人，其中一定有三个人，他们之间或者互相认识，或者互相不认识.

证明：略.

例5、平面上有1987个点，任取三个点中都有两点的距离小于1. 求证：存在半径为1的圆，它至少盖住994个点.

证明：在所给的1987个点中任选一点，记为A，以A为圆心作一个半径为1的圆，若其余的1986个点都在圆A内，则结论成立.否则，在圆A外的点中任一点，记为B，以B为圆心作一个半径为1的圆，则除去A、B之外的其余1985个点必在圆A或圆B内，否则，至少存在一点C在圆A或圆B的外部，则A、B、C三点任两点间的距离均大于1，与条件矛盾，所以除去A、B之外的其余1985个点必在圆A或圆B内.据抽屉原理：必有一个圆内至少有个点，加上圆心共994个点. 知结论成立.

6、小结

7、作业  P26：32、34、39、41

 

第二篇：初等数论教案

                                                                                                                                                                                                                                                                                                                                                                 第一章  整除理论

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

第一节  数的整除性

定义1  设a，b是整数，b¹ 0，如果存在整数c，使得

a = bc

成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b½a；如果不存在整数c使得a = bc成立，则称a不被b整除，记为ba。

显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1  下面的结论成立：

(ⅰ)  a½bÛ±a½±b；

(ⅱ)  a½b，b½cÞa½c；

(ⅲ)  b½a_i，i = 1, 2, L, kÞb½a₁x₁+a₂x₂+L+a_kx_k，此处x_i（i = 1, 2, L, 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不是素数，那么它有两个以上的正的非平凡约数，设它们是d₁, d₂, L, d_k 。不妨设d₁是其中最小的。若d₁不是素数，则存在e₁ > 1，e₂ > 1，使得d₁ = e₁e₂，因此，e₁和e₂也是a的正的非平凡约数。这与d₁的最小性矛盾。所以d₁是素数。证毕。

推论  任何大于1的合数a必有一个不超过的素约数。

证明  使用定理2中的记号，有a = d₁d₂，其中d₁ > 1是最小的素约数，所以d₁²£a。证毕。

例1  设r是正奇数，证明：对任意的正整数n，有

n+ 21^r+ 2^r+L+n ^r。

解  对于任意的正整数a，b以及正奇数k，有

a^k+b^k = (a+b)(a^{k- 1}-a^{k- 2}b+a^{k- 3}b²-L+b^{k- 1}) = (a+b)q，

其中q是整数。记s = 1^r+ 2^r+L+n ^r，则

2s = 2 + (2^r+n ^r) + (3^r+ (n- 1)^r) +L+ (n ^r+ 2^r) = 2 + (n+ 2)Q，

其中Q是整数。若n+ 2½s，由上式知n+ 2½2，因为n+ 2 > 2，这是不可能的，所以n+ 2s。

例2  设A = { d₁, d₂, L, d_k }是n的所有约数的集合，则

B =

也是n的所有约数的集合。

解  由以下三点理由可以证得结论：

(ⅰ)  A和B的元素个数相同；

(ⅱ)  若d_iÎA，即d_i½n，则n，反之亦然；

(ⅲ)  若d_i¹d_j，则。

例3  以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3，L。问：

d(1) +d(2) +L+d(1997)

是否为偶数？

解  对于n的每个约数d，都有n = d×，因此，n的正约数d与是成对地出现的。只有当d =，即n = d²时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。

因为44² < 1997 < 45²，所以在d(1), d(2), L, d(1997)中恰有44个奇数，故d(1) +d(2) +L+d(1997)是偶数。

例4  设凸2n边形M的顶点是A₁, A₂, L, A_2n，点O在M的内部，用1, 2, L, 2n将M的2n条边分别编号，又将OA₁, OA₂, L, OA_2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA₁A₂, OA₂A₃, L, OA_2nA₁的周长都相等。

解  假设这些三角形的周长都相等，记为s。则

2ns = 3(1 + 2 +L+ 2n) = 3n(2n+ 1)，

即

2s = 3(2n+ 1)，

因此2½3(2n+ 1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。

例5  设整数k³ 1，证明：

(ⅰ)  若2^k£n < 2^{k + 1}，1 £a£n，a ¹ 2^k，则2^ka；

(ⅱ)  若3^k£ 2n- 1 < 3^{k + 1}，1 £b£n，2b- 1¹ 3^k，则3^k2b- 1。

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

(ⅱ)  若 3^k|2b-1，则存在整数q，使得2b-1=q3^k，显然q只可能是0，1, 或2。此时2b-1= 0，3^k，或，这都是不可能的，所以3^k2b- 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是素数；

  LL

照以上步骤可以依次得到素数2, 3, 5, 7, 11, L。

由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。

在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。

例7  证明：存在无穷多个正整数a，使得

n⁴+a（n = 1, 2, 3, L）

都是合数。

解  取a = 4k⁴，对于任意的nÎN，有

n⁴+ 4k⁴ = (n²+ 2k²)²- 4n²k² = (n²+ 2k²+ 2nk)(n²+ 2k²- 2nk)。

因为

n²+ 2k²- 2nk = (n-k)²+k²³k²，

所以，对于任意的k = 2, 3, L以及任意的nÎN，n⁴+a是合数。

例8  设a₁, a₂, L, a_n是整数，且

a₁+a₂+L+a_n = 0，a₁a₂La_n = n，

则4½n。

解  如果2n，则n, a₁, a₂, L, a_n都是奇数。于是a₁+a₂+L+a_n是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2½n，即在a₁, a₂, L, a_n中至少有一个偶数。如果只有一个偶数，不妨设为a₁，那么2a_i（2 £i£n）。此时有等式

a₂+L+a_n = -a₁，

在上式中，左端是(n- 1)个奇数之和，右端是偶数，这是不可能的，因此，在a₁, a₂, L, a_n中至少有两个偶数，即4½n。

例9  若n是奇数，则8½n²- 1。

解  设n = 2k+ 1，则

n²- 1= (2k+ 1)²- 1 = 4k(k+ 1)。

在k和k+ 1中有一个是偶数，所以8½n²- 1。

例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：

问题  d(1)²+d(2)²+L+d(1997)²被4除的余数是多少？

例10  证明：方程

a₁²+a₂² + a₃² = 1999                   (1)

无整数解。

解  若a₁，a₂，a₃都是奇数，则存在整数A₁，A₂，A₃，使得

a₁² = 8A₁+ 1，a₂² = 8A₂+ 1，a₃² = 8A₃+ 1，

于是

a₁²+a₂² + a₃² = 8(A₁ + A₂ + A₃) + 3。

由于1999被8除的余数是7，所以a₁，a₂，a₃不可能都是奇数。

由式(1)，a₁，a₂，a₃中只能有一个奇数，设a₁为奇数，a₂，a₃为偶数，则存在整数A₁，A₂，A₃，使得

a₁² = 8A₁+ 1，a₂² = 8A₂+r，a₃² = 8A₃+s，

于是

a₁²+a₂² + a₃² = 8(A₁ + A₂ + A₃) + 1 +r+s，

其中r和s是整数，而且只能取值0或4。这样a₁²+a₂²+a₃²被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a₁，a₂，a₃也不能使式(2)成立。

综上证得所需要的结论。

习 题 一

1.  证明定理1。

2.  证明：若m-p½mn+pq，则m-p½mq+np。

3.  证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。

4.  设p是n的最小素约数，n = pn₁，n₁ > 1，证明：若p >，则n₁是素数。

5.  证明：存在无穷多个自然数n，使得n不能表示为

a²+p（a > 0是整数，p为素数）

的形式。

第二节  带余数除法

在本节中，我们要介绍带余数除法及其简单应用。

定理1(带余数除法)  设a与b是两个整数，b¹ 0，则存在唯一的两个整数q和r，使得

a = bq+r，0 £r < |b|。                  (1)

证明  存在性  若b½a，a = bq，qÎZ，可取r = 0。若ba，考虑集合

A = { a +kb；kÎZ },

其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。

    在集合A中有无限多个正整数，设最小的正整数是r = a +k₀b，则必有

0 < r < |b|，                       (2)

否则就有r ³ |b|。因为ba，所以r¹ |b|。于是r > |b|，即a +k₀b > |b|，a +k₀b- |b| > 0，这样，在集合A中，又有正整数a +k₀b- |b| < r，这与r的最小性矛盾。所以式(2)必定成立。取q = - k₀知式(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 = a₁m+r₁，0 £r₁ < m，

b = b₁m+r₂，0 £r₂ < m，

则ax +by和ab被m除的余数分别与r₁x +r₂y和r₁r₂被m除的余数相同。特别地，a^k与r₁^k被m除的余数相同。

解  由

ax +by = (a₁m+r₁)x+ (b₁m+r₂)y = (a₁x +b₁y)m +r₁x +r₂y

可知，若r₁x +r₂y被m除的余数是r，即

r₁x +r₂y = qm +r，0 £r < m，

则

ax +by = (a₁x +b₁y +q)m +r，0 £r < m，

即ax +by被m除的余数也是r。

同样方法可以证明其余结论。

例2  设a₁, a₂, L, a_n为不全为零的整数，以y₀表示集合

A = { y；y = a₁x₁+L+ a_nx_n，x_iÎZ，1 £i£n }

中的最小正数，则对于任何yÎA，y₀½y；特别地，y₀½a_i，1 £i£n。

解  设y₀ = a₁x₁¢+L+ a_nx_n¢，对任意的y = a₁x₁+L+ a_nx_nÎA，由定理1，存在q, r₀ÎZ，使得

y = qy₀+r₀，0 £r₀ < y₀ 。

因此

r₀ = y-qy₀ = a₁(x₁-qx₁¢)+L+ a_n(x_n-qx_n¢)ÎA。

如果r₀¹ 0，那么，因为0 < r₀ < y₀，所以r₀是A中比y₀还小的正数，这与y₀的定义矛盾。所以r₀ = 0，即y₀½y。

显然a_iÎA（1 £i£n），所以y₀整除每个a_i（1 £i£n）。

例3  任意给出的五个整数中，必有三个数之和被3整除。

解  设这五个数是a_i，i = 1, 2, 3, 4, 5，记

a_i = 3q_i+r_i，0 £ r_i < 3，i = 1, 2, 3, 4, 5。

分别考虑以下两种情形：

(ⅰ)  若在r₁, r₂, L, r₅中数0，1，2都出现，不妨设r₁ = 0，r₂ = 1，r₃ = 2，此时

a₁+a₂+ a₃ = 3(q₁+q₂+q₃)+ 3

可以被3整除；

(ⅱ)  若在r₁, r₂, L, r₅中数0，1，2至少有一个不出现，这样至少有三个r_i要取相同的值，不妨设r₁ = r₂ = r₃ = r（r = 0，1或2），此时

a₁+a₂+ a₃ = 3(q₁+q₂+q₃)+ 3r

可以被3整除。

例4  设a₀, a₁, L, a_nÎZ，f(x) = a_nxⁿ+L+a₁x +a₀ ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则

3½f(-1) = a₀-a₁+ a₂-L+ (-1)ⁿa_n。

解  对任何整数x，都有

x = 3q +r，r = 0，1或2，qÎZ。

(ⅰ)  若r = 0，即x = 3q，qÎZ，则

f(x) = f(3q) = a_n(3q)ⁿ+L+a₁(3q)+a₀ = 3Q₁+ a₀ = 3Q₁+ f(0)，

其中Q₁ÎZ，由于f(0)不是3的倍数，所以f(x) ¹ 0；

(ⅱ)  若r = 1，即x = 3q + 1，qÎZ，则

f(x) = f(3q + 1) = a_n(3q + 1)ⁿ+L+a₁(3q + 1)+a₀

= 3Q₂+a_n+L+a₁+ a₀ = 3Q₂+ f(1)，

其中Q₂ÎZ。由于f(1)不是3的倍数，所以f(x) ¹ 0。

因此若f(x) = 0有整数解x，则必是x = 3q + 2 = 3q¢- 1，q¢ÎZ，于是

0 = f(x) = f(3q¢- 1) = a_n(3q¢- 1)ⁿ+L+a₁(3q¢- 1)+a₀

= 3Q₃+ a₀-a₁+ a₂-L+ (- 1)ⁿa_n = 3Q₃+ f(-1)，

其中Q₃ÎZ。所以3½f(-1) = a₀-a₁+a₂-L+ (-1)ⁿa_n 。

例5  证明：对于任意的整数n，f(n) = 3n⁵+ 5n³+ 7n被15整除。

解  对于任意的正整数n，记

n = 15q +r，0 £r < 15。

由例1，

n² = 15Q₁+r₁，n⁴ = 15Q₂+r₂，

其中r₁与r₂分别是r²与r⁴被15除的余数。

以R表示3n⁴+ 5n²+ 7被15除的余数，则R就是3r₂+ 5r₁+ 7被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R¢。

当r = 0时，显然R¢ = 0，即15½3n⁵+ 5n³+ 7n。

对于r = 1, 2, 3, L, 14的情形，通过计算列出下表：

 r =  1, 14   2, 13   3, 12   4, 11    5, 10   6, 9    7, 8

r₁ =   1      4      9      1      10      6      4

r₂ =   1      1      6      1      10      6      1

R =   0      0     10      0      12     10      0

R¢=   0      0      0      0       0      0      0

这证明了结论。

例6  设n是奇数，则16½n⁴+ 4n²+ 11。

解  我们有

n⁴+ 4n²+ 11 = (n²- 1)(n²+ 5)+ 16。

由第一节例题9，有8½n²- 1，由此及2½n²+ 5得到16½(n²- 1)(n²+ 5)。

例7  证明：若a被9除的余数是3，4，5或6，则方程x³+y³ = a没有整数解。

解  对任意的整数x，y，记

x = 3q₁+r₁，y = 3q₂+r₂，0 £r₁, r₂ < 3。

则存在Q₁, R₁, Q₂, R₂ÎZ，使得

x³ = 9Q₁+R₁，y³ = 9Q₂+R₂ ，

其中R₁和R₂被9除的余数分别与r₁³和r₂³被9除的余数相同，即

R₁ = 0，1或8，R₂ = 0，1或8。              (4)

因此

x³+y³ = 9(Q₁+Q₂)+R₁+R₂ 。

又由式(4)可知，R₁+R₂被9除的余数只可能是0，1，2，7或8，所以，x³+y³不可能等于a。

习 题 二

1.  证明：12½n⁴+ 2n³+ 11n²+ 10n，nÎZ。

2.  设3½a²+b²，证明：3½a且3½b。

3.  设n，k是正整数，证明：n^k与n^{k + 4}的个位数字相同。

4.  证明：对于任何整数n，m，等式n²+ (n + 1)² = m²+ 2不可能成立。

5.  设a是自然数，问a⁴- 3a²+ 9是素数还是合数？

6.  证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。

第三节  最大公约数

定义1  整数a₁, a₂, L, a_k的公共约数称为a₁, a₂, L, a_k的公约数。不全为零的整数a₁, a₂, L, a_k的公约数中最大的一个叫做a₁, a₂, L, a_k的最大公约数（或最大公因数），记为(a₁, a₂, L, a_k)。

由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。

如果(a₁, a₂, L, a_k)=1，则称a₁, a₂, L, a_k是互素的（或互质的）；如果

(a_i, a _j)=1，1 £i, j £k，i¹ j，

则称a₁, a₂, L, a_k是两两互素的（或两两互质的）。

显然，a₁, a₂, L, a_k两两互素可以推出(a₁, a₂, L, a_k) =1，反之则不然，例如(2, 6, 15)=1，但(2, 6) = 2。

定理1  下面的等式成立：

(ⅰ)  (a₁, a₂, L, a_k)=(|a₁|, |a₂|, L, |a_k|)；

(ⅱ)  (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可知，在讨论(a₁, a₂, L, a_n)时，不妨假设a₁, a₂, L, a_n是正整数，以后我们就维持这一假设。

定理2  设a₁, a₂, L, a_kÎZ，记

A ={ y；y =，x_iÎZ，1£i£k }。

如果y₀是集合A中最小的正数，则y₀=(a₁, a₂, L, a_k)。

证明  设d是a₁, a₂, L, a_k的一个公约数，则d½y₀，所以d£y₀。另一方面，由第二节例2知，y₀也是a₁, a₂, L, a_k的公约数。因此y₀是a₁, a₂, L, a_k的公约数中的最大者，即y₀=( a₁, a₂, L, a_k)。证毕。

推论1  设d是a₁, a₂, L, a_k的一个公约数，则d½(a₁, a₂, L, a_k)。

这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。

推论2  (ma₁, ma₂, L, ma_k)=|m|(a₁, a₂, L, a_k)。

推论3  记d=(a₁, a₂, L, a_k)，则

= 1，

特别地, = 1。

定理3  (a₁, a₂, L, a_k)=1的充要条件是存在整数x₁, x₂, L, x_k，使得

a₁x₁+ a₂x₂+L+ a_kx_k=1。                (1)

证明  必要性  由定理2得到。

充分性  若式(1)成立，如果 (a₁, a₂, L, a_k)= d > 1，那么由d½a_i（1 £i £k）推出d½a₁x₁+a₂x₂+L+a_kx_k=1，这是不可能的。所以有(a₁, a₂, L, a_k)= 1。证毕。

定理4  对于任意的整数a，b，c，下面的结论成立：

(ⅰ)  由b½ac及(a, b)=1可以推出b½c；

(ⅱ)  由b½c，a½c及(a, b)=1可以推出ab½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½a²Þp½a。

证明  留作习题。

推论2  若 (a, b)=1，则(a, bc)=(a, c)。

证明  设d是a与bc的一个公约数，则d½a，d½bc，由式（2）得到，d|c, 即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a, bc)=(a, c)。证毕。

推论3  若 (a, b_i)=1，1 £i£n，则(a, b₁b₂Lb_n)=1。

证明  留作习题。

定理5  对于任意的n个整数a₁, a₂, L, a_n，记

(a₁, a₂)= d₂，(d₂, a₃)= d₃，L，(d_{n - 2}, a_{n - 1})= d_{n - 1}，(d_{n - 1}, a_n)= d_n，

则

d_n=(a₁, a₂, L, a_n)。

证明  由定理2的推论，我们有

    d_n=(d_{n - 1}, a_n) Þd_n½a_n，d_n½d_{n - 1}，

d_{n - 1}=(d_{n - 2}, a_{n - 1}) Þd_{n - 1}½a_{n - 1}，d_{n - 1}½d_{n - 2}，

                Þd_n½a_n，d_n½a_{n - 1}，d_n½d_{n - 2}，

d_{n - 2}=(d_{n - 3}, a_{n - 2}) Þd_{n - 2}½a_{n - 2}，d_{n - 2}½d_{n - 3}

                Þd_n½a_n，d_n½a_{n - 1}，d_n½a_{n - 2}，d_n½d_{n - 3}，

LL

      d₂=(a₁, a₂) Þ d_n½a_n，d_n½a_{n - 1}，L，d_n½a₂，d_n½a₁，

即d_n是a₁, a₂, L, a_n的一个公约数。

另一方面，对于a₁, a₂, L, a_n的任何公约数d，由定理2的推论及d₂, L, d_n的定义，依次得出

 d½a₁，d½a₂Þd½d₂，

 d½d₂，d½a₃Þd½d₃，

LL

d½d_{n - 1}，d½a_nÞd½d_n，

因此d_n是a₁, a₂, L, a_n的公约数中的最大者，即d_n=(a₁, a₂, L, a_n)。证毕。

例1  证明：若n是正整数，则是既约分数。

解  由定理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)，

因此，是既约分数。

例2  证明：121n²+2n +12，nÎZ。

解  由于121=11²，n²+2n +12=(n +1)²+11，所以，若

11²½(n +1)²+11，                    (3)

则11½(n +1)²，因此，由定理4的推论1得到

11½n +1，11²½(n +1)²。

再由式(3)得到

11²½11，

这是不可能的。所以式(3)不能成立。

注：这个例题的一般形式是：

设p是素数，a，b是整数，则

p^k(an + b)^k+ p^{k - 1c}，

其中c是不被p整除的任意整数，k是任意的大于1的整数。

例3  设a，b是整数，且

9½a²+ ab + b²，                     (4)

则3½(a, b)。

解  由式(4)得到

9½(a -b)²+3abÞ 3½(a -b)²+3ab

Þ 3½(a -b)²Þ3½a -b              (5)

Þ 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)。

例4  设a和b是正整数，b > 2，则2^b- 12^a+1。

解  (ⅰ)  若a < b，且

2^b- 1½2^a+1。                      (6)

成立，则

2^b- 1 £ 2^a+1 Þ 2^b- 2^a£ 2 Þ 2^a(2^{b -a}- 1) £ 2，

于是a = 1，b -a = 1，即b = 2，这是不可能的，所以式(6)不成立。

(ⅱ)  若a = b，且式(6)成立，则由式(6)得到

2^a- 1½(2^a- 1)+2 Þ 2^a- 1½2 Þ 2^a- 1 £ 2 Þ 2^a£ 3，

于是b = a = 1，这是不可能的，所以式(6)不成立。

(ⅲ)  若a > b，记a = kb + r，0 £r < b，此时

2^kb- 1=(2^b- 1)(2^{(k - 1)b}+2^{(k - 2)b}+L+1)=(2^b- 1)Q，

其中Q是整数。所以

2^a+1=2^{kb + r}+1=2^r(2^kb- 1+1)+1

 =2^r((2^b- 1)Q +1)+1 = (2^b- 1)Q¢+(2^r+1)，

其中Q¢是整数。因此

2^b- 1½2^a+1 Þ 2^b- 1½2^r+1，

在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立。

综上证得2^b- 12^a+1。

习 题 三

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无平方因子，a²½b²c，证明：a½b。

6.  设n是正整数，求的最大公约数。

第四节  最小公倍数

定义1  整数a₁, a₂, L, a_k的公共倍数称为a₁, a₂, L, a_k的公倍数。a₁, a₂, L, a_k的正公倍数中的最小的一个叫做a₁, a₂, L, a_k的最小公倍数，记为[a₁, a₂, L, a_k]。

定理1  下面的等式成立：

(ⅰ)  [a, 1] = |a|，[a, a] = |a|；

(ⅱ)  [a, b] = [b, a]；

(ⅲ)  [a₁, a₂, L, a_k] = [|a₁|,|a₂| L, |a_k|]；

(ⅳ)  若a½b，则[a, b] = |b|。

证明  留作习题。

由定理1中的结论(ⅲ)可知，在讨论a₁, a₂, L, a_k的最小公倍数时，不妨假定它们都是正整数。在本节中总是维持这一假定。

最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。

定理2  对任意的正整数a，b，有

[a, b] =。

证明  设m是a和b的一个公倍数，那么存在整数k₁，k₂，使得m = ak₁，m = bk₂，因此

ak₁ = bk₂ 。                       (1)

于是

。

由于= 1，所以由第三节定理4得到

，

其中t是某个整数。将上式代入式(1)得到

m =t。                      (2)

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

[a, b] =。

证毕。

推论1  两个整数的任何公倍数可以被它们的最小公倍数整除。

证明  由式(2)可得证。证毕。

这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。

推论2  设m，a，b是正整数，则[ma, mb] = m[a, b]。

证明  由定理2及第三节定理2的推论得到

[ma, mb] == m[a, b]。

证毕。

定理3  对于任意的n个整数a₁, a₂, L, a_n，记

[a₁, a₂] = m₂，[m₂, a₃] = m₃，L，[m_n-2, a_n-1] = m_n-1，[m_n-1, a_n] = m_n，

则

[a₁, a₂, L, a_n] = m_n。

证明  我们有

   m_n = [m_n-1, a_n] Þm_n-1½m_n，a_n½m_n，

m_n-1 = [m_n-2, a_n-1] Þm_n-2½m_n-1½m_n，a_n½m_n，a_n-1½m_n-1½m_n，

m_n-2 = [m_n-3, a_n-2] Þm_n-3½m_n-2½m_n，a_n½m_n，a_n-1½m_n，a_n-2½m_n，

LL

    m₂ = [a₁, a₂] Þa_n½m_n，L，a₂½m_n，a₁½m_n，

即m_n是a₁, a₂, L, a_n的一个公倍数。

另一方面，对于a₁, a₂, L, a_n的任何公倍数m，由定理2的推论及m₂, L, m_n的定义，得

m₂½m，m₃½m，L，m_n½m。

即m_n是a₁, a₂, L, a_n最小的正的公倍数。证毕。

推论  若m是整数a₁, a₂, L, a_n的公倍数，则[a₁, a₂, L, a_n]½m。

证明  留作习题。

定理4  整数a₁, a₂, L, a_n两两互素，即

(a_i, a_j) = 1，1 £i, j £n，i ¹j

的充要条件是

[a₁, a₂, L, a_n] = a₁a₂La_n 。                 (3)

证明  必要性  因为(a₁, a₂) = 1，由定理2得到

[a₁, a₂] == a₁a₂ 。

由(a₁, a₃) = (a₂, a₃) = 1及第三节定理4推论3得到

(a₁a₂, a₃) = 1，

由此及定理3得到

[a₁, a₂, a₃] = [[a₁, a₂], a₃] = [a₁a₂, a₃] = a₁a₂a₃ 。

如此继续下去，就得到式(3)。

充分性  用归纳法证明。当n = 2时，式(3)成为[a₁, a₂] = a₁a₂。由定理2

a₁a₂ = [a₁, a₂] =Þ (a₁, a₂) = 1，

即当n = 2时，充分性成立。

假设充分性当n = k时成立，即

[a₁, a₂, L, a_k] = a₁a₂La_kÞ (a_i, a_j) = 1，1 £i, j £k，i ¹j。

对于整数a₁, a₂, L, a_k, a_{k + 1}，使用定理3中的记号，由定理3可知

[a₁, a₂, L, a_k, a_{k + 1}] = [m_k, a_{k + 1}]。                (4)

其中m_k = [a₁, a₂, L, a_k]。因此，如果

[a₁, a₂, L, a_k, a_{k + 1}] = a₁a₂La_ka_{k + 1}，

那么，由此及式(4)得到

[a₁, a₂, L, a_k, a_{k + 1}] = [m_k, a_{k + 1}] == a₁a₂La_ka_{k + 1}，

即

= a₁a₂La_k，

显然m_k£ a₁a₂La_k，(m_k, a_{k + 1}) ³ 1。所以若使上式成立，必是

(m_k, a_{k + 1}) = 1，                     (5)

并且

m_k = a₁a₂La_k 。                    (6)

由式(6)与式(5)推出

(a_i, a_{k + 1}) = 1，1 £i£k；                (7)

由式(6)及归纳假设推出

(a_i, a_j) = 1，1 £i, j £k，i ¹j。              (8)

综合式(7)与式(8)，可知当n = k+ 1时，充分性成立。由归纳法证明了充分性。证毕。

定理4有许多应用。例如，如果m₁, m₂, L, m_k是两两互素的整数，那么，要证明m = m₁m₂Lm_k整除某个整数Q，只需证明对于每个i，1 £i£k，都有m_i½Q。这一点在实际计算中是很有用的。对于函数f(x)，要验证命题“m½f(n)，nÎZ”是否成立，可以用第二节例5中的方法，验证“m½f(r)，r = 0, 1, L, m- 1”是否成立。这需要做m次除法。但是，若分别验证“m_i½f(r_i)，r_i = 0, 1, L, m_i- 1，1 £i£k”是否成立，则总共需要做m₁+m₂+L+m_k次除法。后者的运算次数显然少于前者。

例1  设a，b，c是正整数，证明：[a, b, c](ab, bc, ca) = abc。

解  由定理3和定理2有

[a, b, c] = [[a, b], c] =，             (9)

由第三节定理5和定理2的推论，

(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b))

=。   (10)

联合式(9)与式(10)得到所需结论。

例2  对于任意的整数a₁, a₂, L, a_n及整数k，1 £k £n，证明：

[a₁, a₂, L, a_n] = [[a₁,L, a_k],[a_{k + 1}, L, a_n]]

解  因为[a₁, a₂, L, a_n]是a₁, L, a_k, a_{k + 1}, L, a_n的公倍数，所以由定理2推论，推出

[a₁, L, a_k]½[a₁, a₂, L, a_n]，

[a_{k + 1}, L, a_n]½[a₁, a₂, L, a_n]，

再由定理3推论知

[[a₁, L, a_k], [a_{k + 1}, L, a_n]]½[a₁, a₂, L, a_n]。        (11)

另一方面，对于任意的a_i（1 £i£n），显然

a_i½[[a₁, L, a_k], [a_{k + 1}, L, a_n]]，

所以由定理3推论可知

[a₁, a₂, L, a_n]½[[a₁, L, a_k], [a_{k + 1}, L, a_n]]，

联合上式与式(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]

= [[a²b, ab², abc], [abc, b²c, bc²], [a²c, abc, ac²]]

= [a²b, ab², abc, abc, b²c, bc², a²c, abc, ac²]

= [abc, a²b, a²c, b²c, b²a, c²a, c²b]

以及

[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a]

= [ab, b², ac, bc][c, a]

= [ab[c, a], b²[c, a], ac[c, a], bc[c, a]]

= [abc, a²b, b²c, b²a, ac², a²c, bc², bca]

= [abc, a²b, a²c, b²c, b²a, 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是正整数，证明：

。

    6.  设k是正奇数，证明：1 + 2 +L+ 9½1^k+ 2^k+L+ 9^k。

第五节  辗转相除法

本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。

定义1  下面的一组带余数除法，称为辗转相除法。

设a和b是整数，b ¹ 0，依次做带余数除法：

   a = bq₁+r₁，    0 < r₁ < |b|，

   b = r₁q₂+r₂，    0 < r₂ < r₁ ，

LL

 r_{k - 1} = r_kq_{k + 1}+r_{k + 1}，0 < r_{k + 1} < r_k，             (1)

LL

 r_{n - 2} = r_{n - 1}q_n+r_n，  0 < r_n < r_n-1 ，

 r_{n - 1} = r_nq_{n + 1} 。

由于b是固定的，而且

|b| > r₁ > r₂ > L，

所以式(1)中只包含有限个等式。

下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。

引理1  用下面的方式定义Fibonacci数列{F_n}：

F₁ = F₂ = 1，F_n = F_{n - 1}+F_{n- 2}，n ³3，

那么对于任意的整数n ³ 3，有

F_n > a^{n - 2}，                      (2)

其中a=。

证明  容易验证

a² = a+ 1。

当n = 3时，由

F₃ = 2 >= a

可知式(2)成立。

假设式(2)对于所有的整数k £n（n ³ 3）成立，即

F_k> a^{k - 2}，k £n，

则

F_{n + 1} = F_n+F_{n - 1} > a ^{n - 2}+a ^{n - 3} = a ^{n - 3}(a+ 1) = a ^{n - 3}a² = a ^{n- 1}，

即当k = n+ 1时式(2)也成立。由归纳法知式(2)对一切n ³ 3成立。证毕。

定理1(Lame)  设a, bÎN，a > b，使用在式(1)中的记号，则

n < 5log₁₀b。

证明  在式(1)中，r_n³ 1，q_{n + 1}³ 2，q_i³ 1（1 £i £n），因此

r_n³ 1 = F₂ ，

r_{n - 1}³ 2r_n³ 2 = F₃ ，

r_{n - 2}³r_{n - 1}+r_n³F₃ + F₂ = F₄ ，

LL

b ³r₁+r₂³F_{n + 1}+F_n = F_{n + 2} ，

由此及式(2)得

b³aⁿ =，

即

log₁₀b³nlog₁₀，

这就是定理结论。证毕。

定理2  使用式(1)中的记号，记

P₀ = 1，P₁ = q₁，P_k = q_kP_{k - 1}+P_{k - 2}，k ³ 2，

Q₀ = 0，Q₁ = 1，Q_k = q_kQ_{k - 1}+Q_{k - 2}，k ³ 2，

则

aQ_k-bP_k = (-1)^{k - 1}r_k，k = 1, 2, L, n 。           (3)

证明  当k = 1时，式(3)成立。

当k = 2时，有

Q₂ = q₂Q₁+Q₀ = q₂，P₂ = q₂P₁+P₀ = q₂q₁+ 1，

此时由式(1)得到

aQ₂-bP₂ = aq₂-b(q₂q₁+ 1) = (a -bq₁)q₂-b = r₁q₂-b =-r₂，

即式(3)成立。

假设对于k < m（1 £m £n）式(3)成立，由此假设及式(1)得到

 aQ_m-bP_m= a(q_mQ_{m - 1}+Q_{m - 2})-b(q_mP_{m - 1}+P_{m - 2})

= (aQ_{m - 1}-bP_{m - 1})q_m+ (aQ_{m - 2}-bP_{m - 2})

= (-1)^{m - 2}r_{m - 1}q_m+ (-1)^{m - 3}r_{m - 2}

= (-1)^{m - 1}(r_{m - 2}-r_{m - 1}q_m) = (-1)^{m- 1}r_m，

即式(3)当k = m时也成立。定理由归纳法得证。证毕。

定理3  使用式(1)中的记号，有r_n = (a, b)。

证明  由第三节定理1，从式(1)可见

r_n = (r_{n - 1}, r_n) = (r_{n - 2}, r_{n - 1}) = L = (r₁, r₂) = (b, r₁) = (a, b)。

证毕。

现在我们已经知道，利用辗转相除法可以求出整数x，y，使得

ax+by = (a, b)。                    (4)

为此所需要的除法次数是O(log₁₀b)。但是如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。

例1  设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a, b)。

解  下面的四个基本事实给出了证明：

(ⅰ)  若a½b，则(a, b) = a；

(ⅱ)  若a = 2^aa₁，，a³b³ 1，则

(a, b) = 2^b(2^a-ba₁, b₁)；

(ⅲ)  若，则(a, b) = (a, b₁)；

(ⅳ)  若。

在实际计算过程中，若再灵活运用最大公约数的性质（例如第三节定理4的推论），则可使得求最大公约数的过程更为简单。

例2  用辗转相除法求(125, 17)，以及x，y，使得

125x+ 17y = (125, 17)。

解  做辗转相除法：

125 = 7×17 + 6，q₁ = 7，r₁ = 6，

 17 = 2×6 + 5，q₂ = 2，r₂ = 5，

  6 = 1×5 + 1，q₃ = 1，r₃ = 1，

  5 = 5×1，    q₄ = 5。

由定理4，(125, 17) = r₃ = 1。

利用定理2计算（n = 3）

P₀ = 1，P₁ = 7，P₂ = 2×7 + 1 = 15，P₃ = 1×15 + 7 = 22，

Q₀ = 0，Q₁ = 1，Q₂ = 2×1 + 0 = 2，Q₃ = 1×2 + 1 = 3，

取x = (-1)^{3 - 1}Q₃ = 3，y = (-1)³P₃ = -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个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n（n < m）个盒子中各放一个硬币。证明：若(m, n) = 1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币。

解  由于(m, n) = 1，所以存在整数x，y，使得mx+ny = 1。因此对于任意的自然数k，有

1 +m(-x+kn) = n(km+y)，

这样，当k充分大时，总可找出正整数x₀，y₀，使得

1 +mx₀ = ny₀ 。

上式说明，如果放y₀次（每次放n个），那么在使m个盒子中各放x₀个后，还多出一个硬币。把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1。因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同。

习 题 五

1.  说明例1证明中所用到的四个事实的依据。

2.  用辗转相除法求整数x，y，使得1387x - 162y = (1387, 162)。

3.  计算：(27090, 21672, 11352)。

4.  使用引理1中的记号，证明：(F_{n + 1}, F_n) = 1。

5.  若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少？

6.  记M_n=2ⁿ- 1，证明：对于正整数a，b，有(M_a, M_b)= M_{(a, b)}。

第六节  算术基本定理

在本节中，我们要介绍整数与素数的一个重要关系，即任何大于1的正整数都可以表示成素数的乘积。

引理1  任何大于1的正整数n可以写成素数之积，即

n = p₁p₂Lp_m，                      (1)

其中p_i（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，由归纳假定知存在素数q₁, q₂, L, q_l，使得d = q₁q₂Lq_l，从而k+ 1 = pq₁q₂Lq_l。证毕。

定理1(算术基本定理)  任何大于1的整数n可以唯一地表示成

n =，                   (2)

其中p₁, p₂, L, p_k是素数，p₁ < p₂ < L < p_k，a₁, a₂, L, a_k是正整数。

证明  由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，只需证明表示式(2)的唯一性。

假设p_i（1 £i £k）与q_j（1 £j £l）都是素数，

p₁£p₂£L£p_k，q₁£q₂£L£q_l，            (3)

并且

n = p₁p₂Lp_k = q₁q₂Lq_l ，                 (4)

则由第三节定理4推论1，必有某个q_j（1 £j£l），使得p₁½q_j，所以p₁ = q_j；又有某个p_i（1 £i£k），使得q₁½p_i，所以q₁ = p_i。于是，由式(3)可知p₁ = q₁，从而由式(4)得到

p₂Lp_k = q₂Lq_l 。

重复上述这一过程，得到

k = l，p_i = q_i，1 £i £k。

证毕。

定义1  使用定理1中的记号，称

n =

是n的标准分解式，其中p_i（1 £i £k）是素数，p₁ < p₂ < L < p_k，a _i（1 £i £k）是正整数。

推论1  使用式(2)中的记号，有

(ⅰ)  n的正因数d必有形式

d =，g_iÎZ，0 £g_i£a _i，1 £i £k；

(ⅱ)  n的正倍数m必有形式

m =M，MÎN，b_iÎN，b_i³a _i，1 £i £k。

证明  留作习题。

推论2  设正整数a与b的标准分解式是

其中p_i（1 £i £k），q_i（1 £i £l）与r_i（1 £i £s）是两两不相同的素数，a_i，b_i（1 £i £k），g_i（1 £i £l）与d_i（1 £i £s）都是正整数，则

(a, b) =，  l_i = min{a_i, b_i }，1 £i £k，

[a, b] =，m_i = max{a_i, b_i }，1 £i £k。

证明  留作习题。

为了方便，推论2常叙述为下面的形式：

推论2¢  设正整数a与b的标准分解式是

，

其中p₁, p₂, L, p_k是互不相同的素数，a_i，b_i（1 £i £k）都是非负整数，则

推论3  设a，b，c，n是正整数，

ab = cⁿ，(a, b) = 1，                   (5)

则存在正整数u，v，使得

a = uⁿ，b = vⁿ，c = uv，(u, v) = 1。

证明  设c =，其中p₁, p₂, L, p_k是互不相同的素数，g_i（1 £i £k）是正整数。又设

，

其中a_I，b_i（1 £i £k）都是非负整数。由式(5)及推论2¢可知

min{a_i, b_i} = 0，a_i+b_i = ng_i，1 £i £k，

因此，对于每个i（1 £i £k），等式

a_i = ng_i ，b_i = 0与a_i = 0，b_i = ng_i

有且只有一个成立。这就证明了推论。证毕。

例1  写出51480的标准分解式。

解  我们有

51480 = 2×25740 = 2²×12870 = 2³×6435

= 2³×5×1287 = 2³×5×3×429

= 2³×5×3²×143 = 2³×3²×5×11×13。

例2  设a，b，c是整数，证明：

(ⅰ)  (a, b)[a, b] = ab；

(ⅱ)  (a, [b, c]) = [(a, b), (a, c)]。

解  为了叙述方便，不妨假定a，b，c是正整数。

(ⅰ)  设

，

其中p₁, p₂, L, p_k是互不相同的素数，a_i，b_i（1 £i £k）都是非负整数。由定理1推论2¢，有

由此知

(a, b)[a, b] ==ab；

(ⅱ)  设

，

其中p₁, p₂, L, p_k是互不相同的素数，a_i，b_i，g_i（1 £i £k）都是非负整数。由定理1推论2¢，有

，

其中，对于1 £i £k，有

l_i = min{a_i, max{b_i, g_i}}，

m_i = max{min{a_i, b_i}, min{a_i, g_i}}，

不妨设b_i£g_i，则

min{a_i, b_i} £ min{a_i, g_i}，

所以

m_i = min{a_i, g_i} = l_i，

即(a, [b, c]) = [(a, b), (a, c)]。

注：利用定理1可以容易地处理许多像例2这样的问题。

例3  证明：（n ³ 2）不是整数。

解  设

3^k£ 2n - 1 < 3^{k + 1}。

对于任意的1 £i £n，2i - 1 ¹ 3^k，记

2i - 1 =Q_i，Q_iÎZ，

由第一节例5，知a_i£k - 1。因为3^{k - 1}Q₁Q₂LQ_{2n - 1}是整数，所以，如果N是整数，则存在整数Q，使得

3^{k - 1}Q₁Q₂LQ_{2n - 1}N = Q+ 3^{k- 1}Q₁Q₂LQ_{2n -1}。

由于3Q₁Q₂LQ_2n-1，所以上式右端不是整数，这个矛盾说明N不能是整数。

习 题 六

1.  证明定理1的推论1。

2.  证明定理1的推论2。

3.  写出22345680的标准分解式。

4.  证明：在1, 2, L, 2n中任取n+ 1数，其中至少有一个能被另一个整除。

5.  证明：（n ³ 2）不是整数。

6.  设a，b是正整数，证明：存在a₁，a₂，b₁，b₂，使得

a = a₁a₂，b = b₁b₂，(a₂, b₂) = 1，

并且[a, b] = a₂b₂。

第七节  函数[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] =；

(ⅴ)  [-x] =；

(ⅵ)  {-x} =。

证明  留作习题。

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

证明  能被b整除的正整数是b, 2b, 3b, L，因此，若数1, 2, L, a中能被b整除的整数有k个，则

kb £a < (k+ 1)bÞk £< k+ 1 Þk =。

证毕。

由定理2我们看到，若b是正整数，那么对于任意的整数a，有

，

即在带余数除法

a = bq+r，0 £r < b

中有。

定理3  设n是正整数，n! =是n!的标准分解式，则

a_i =。                      (1)

证明  对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则

p(n!) = p(1) +p(2) +L+p(n)。

以n_j表示p(1), p(2), L, p(n)中等于j的个数，那么

p(n!) = 1×n₁+ 2×n₂+ 3×n₃+L，               (2)

显然，n_j就是在1, 2, L, n中满足p^j½a并且p^{j + 1}a的整数a的个数，所以，由定理2有

n_j =。

将上式代入式(2)，得到

即式(1)成立。证毕。

推论  设n是正整数，则

n! =，

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

定理４  设n是正整数，1 £k£n - 1，则

ÎN。                  (3)

若n是素数，则n½，1 £k£n - 1。

证明  由定理3，对于任意的素数p，整数n!，k!与(n -k)!的标准分解式中所含的p的指数分别是

。

利用定理1可知

，

因此是整数。

若n是素数，则对于1 £k £n - 1，有

(n, k!) = 1，(n, (n -k)!) = 1 Þ (n, k!(n -k)!) = 1，

由此及

ÎN，

推出k!(n -k)!½(n - 1)!，从而n½。证毕。

例1  求最大的正整数k，使得10^k½199!。

解  由定理3，199!的标准分解式中所含的5的幂指数是

 = 47，

所以，所求的最大整数是k = 47。

例2  设x与y是实数，则

[2x] + [2y] ³ [x] + [x+y] + [y]。              (4)

解  设x = [x] +a，0 £a < 1，y = [y] +b，0 £b < 1，则

[x] + [x+y] + [y] = 2[x] + 2[y] + [a+b]，           (5)

[2x] + [2y] = 2[x] + 2[y] + [2a] + [2b]。            (6)

如果[a+b] = 0，那么显然有[a+b] £ [2a] + [2b]；

如果[a+b] = 1，那么a与b中至少有一个不小于，于是

[2a] + [2b]³ 1 = [a+b]。

因此无论[a+b] = 0或1，都有[a+b] £ [2a] + [2b]，由此及式(5)和式(6)可以推出式(4)。

例3  设n是正整数，则

。               (7)

解  首先，我们有

所以

。

若上式中的等号不成立，即

，                 (8)

则存在整数a，使得

，

因此

(2n+ 1)²- 1< (a²- 2n- 1)²£ (2n+ 1)²，

所以

a²- 2n - 1 = 2n + 1 Þ a² = 4n+ 2。            (9)

但是，无论2½a或2a，式(9)都不能成立，这个矛盾说明式(8)不能成立，即式(7)成立。

例4  设x是正数，n是正整数，则

= [nx]。

解  设x = [x] +a，，0 £i£n - 1，则

= n[x] +i = n[x] + [na] = [n([x] +a)] = [nx]。

例5  求[]的个位数。

解  由得

               

          =

          =

= 10A+ 2⁹⁹⁷×6⁴⁹⁸ = 10A+ 2×24⁴⁹⁸= 10A+ 2(25- 1)⁴⁹⁸

= 10B+ 2，                                    （10）

其中A和B都是整数。由于0 < 5-< 1，所以，由式(10)可知[]的个位数是1。

注：一般地，如果A，BÎN，A² > B，< 1，则由

可以求出[]。

例6  设x和y是正无理数，，证明：数列

[x], [2x], L, [kx], L与 [y], [2y], L, [my], L          (11)

联合构成了整个正整数集合，而且，两个数列中的数互不相同。

解  显然x > 1，y > 1，并且x ¹y。因此，在数列(11)中至多有一个数等于给定的正整数n，否则存在正整数k与m，使得

n = [kx] = [my]。

因为x与y都是无理数，所以我们有

n < kx < n+ 1，n < my < n+ 1，

n < k+m < n+ 1，

这是不可能的。

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

[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 < n+ 1 < p+q+ 2，

这是不可能的。

习 题 七

1.  证明定理1。

2.  求使12347!被35^k整除的最大的k值。

3.  设n是正整数，x是实数，证明：= n。

4.  设n是正整数，求方程

x²- [x²] = (x - [x])²

在[1, n]中的解的个数。

5.  证明：方程

f(x) = [x] + [2x] + [2²x] + [2³x] + [2⁴x] + [2⁵x] = 12345

没有实数解。

6.  证明：在n!的标准分解式中，2的指数h = n -k，其中k是n的二进制表示的位数码之和。

第八节  素  数

在第六节中我们已经证明了：每个正整数可以表示成素数幂的乘积。这就引出了一个问题：素数是否有无穷多个？如果有无穷多个，那么，作为无穷大量，素数个数具有怎样的性状？这是数论研究中的一个中心课题。本节要对这一问题作初步的研究。

定义1  对于正实数x，以p(x)表示不超过x的素数个数。

例如，p(15) = 6，p(10.4) = 4，p(50) = 15。

定理1  素数有无限多个。

证明  我们给出三个证明方法。

证法Ⅰ  假设只有k个素数，设它们是p₁, p₂, L, p_k。记

N = p₁p₂Lp_k+ 1。

由第一节定理2可知，N有素因数p，我们要说明p ¹p_i，1 £i £k，从而得出矛盾。

事实上，若有某个i，1 £i £k，使得p = p_i，则由

p½N = p₁p₂Lp_k+ 1

推出p½1，这是不可能的。因此在p₁, p₂, L, p_k之外又有一个素数p，这与假设是矛盾的。所以素数不可能是有限个。

证法Ⅱ  我们证明整数

是两两互素的，从而由第六节引理1可知素数有无限多个。

事实上，若m和n是整数，m > n ³ 0，则

此处Q是整数。因此

故

证法Ⅲ  假设只有有限个素数p₁, p₂, L, p_k。由第六节定理1，每个正整数可以写成

n =，a_i³ 1，1 £i£k。

由于

，

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

。

当N®¥时，上式左端是一个无穷大量，右端是有限的，这个矛盾说明素数不能是有限多个。证毕。

注1：形如（n = 0, 1, 2, L）的数称为Fermat数。Fermat曾经猜测它们都是素数。这是错误的，因为尽管F₀，F₁，F₂，F₃，F₄都是素数，F₅ =却是合数。

注2：将全体素数按大小顺序排列为

p₁ = 2，p₂ = 3，p₃ = 5，p₄，L，p_n，L，

那么由第一个证明方法可以看出

p_{n + 1}£p₁p₂Lp_n+ 1，n ³ 1。

定理2  对于n³ 1，

(ⅰ)  p(n) ³log₂n；

(ⅱ)  p_n£ 2²ⁿ。

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

k = a²b，1 £k £n                      (1)

即1 £a²b £n成立的整数a，b有多少对。首先，整数a的个数£；其次，由于b £ n并且不含有平方因数，所以，整数b的因数只可能是不超过n的不同的素数的乘积，因此，整数b的个数£ 2^p(n)。这样，使得式(1)成立的整数a和b至多是2^p(n)对，所以，n£2^p(n)，即p(n) ³log₂n。

(ⅱ)  以p_m表示第m个素数，在结论(ⅰ)中取n = p_m，我们得到m³log₂p_m，由此即可得到结论(ⅱ)。证毕。

注：定理2对于无穷大量p(x)的下界估计是相当粗糙的。下面的定理是已经知道的（由于其证明较繁，故本书中不予证明）。

定理3(素数定理)  我们有

p(x) ~，（x®¥），

此处logx是以e为底的x的对数。

推论  以p_n表示第n个素数，则

p_n~nlogn（n®¥）。

证明  由定理3，当n®¥时，有

n ~。                      (2)

因此

nlogp_n~p_n，

logn+ loglogp_n~ logp_n，

logn ~ logp_n。

由上式与式(2)得p_n~nlogn（n®¥）。证毕。

例1  若a > 1，aⁿ- 1是素数，则a = 2，并且n是素数。

解  若a > 2，则由

aⁿ- 1 = (a - 1)(a^{n - 1}+a^{n - 2}+L+ 1)

可知aⁿ- 1是合数。所以a = 2。

若n是合数，则n = xy，x > 1，y >1，于是由

2^xy- 1 = (2^x- 1)(2^{x(y - 1)}+ 2^{x(y - 2)}+L+ 1)

以及2^x- 1 > 1可知2ⁿ- 1是合数，所以2ⁿ- 1是素数时，n必是素数。

注：若n是素数，则称2ⁿ- 1是Mersenne数。

例2  形如4n+ 3的素数有无限多个。

解  若不然，假设只有k个形如4n+ 3的素数p₁, p₂, L, p_k。记

N = 4p₁pLp_k – 1。

由第六节引理1，正整数N可以写成若干个素数之积。我们指出，这些素因数中至少有一个是4n+ 3形式。否则，若它们都是4n+ 1的形式，则N也是4n+ 1的形式，这与N的定义矛盾。以p表示这个素因数，则p ¹p_i，1 £i £k。否则若有某个i，1 £i £k，使得p = p_i，则由p½N推出p½1，这是不可能的。因此在p₁, p₂, L, p_k之外又存在一个形如4n+ 3的素数p，这与原假设矛盾，所以形如4n+ 3的素数有无限多个。

例3  设f(x) = a_kx^k+a_{k - 1}x^{k - 1}+L+a₀是整系数多项式，那么，存在无穷多个正整数n，使得f(n)是合数。

解  不妨假定a_k > 0。于是f(x)®+¥（x®+¥），因此，存在正整数N，使得当n > N时，有f(n) > 1。取整数x > N，记

y = f(x) = a_kx^k+a_{k - 1}x^{k - 1 +}L+a₀，

又设r是任意的正整数，n = ry+x，则

f(n) = f(ry+x) = a_k(ry+x)^k+a_{k - 1}(ry+x)^{k - 1 +}L+a₀

= yQ+f(x) = y(Q+ 1)

是合数。

习 题 八

1.  证明：若2ⁿ+ 1是素数，则n是2的乘幂。

2.  证明：若2ⁿ- 1是素数，则n是素数。

3.  证明：形如6n+ 5的素数有无限多个。

4.  设d是正整数，6d，证明：在以d为公差的等差数列中，连续三项都是素数的情况最多发生一次。

5.  证明：对于任意给定的正整数n，必存在连续的n个自然数，使得它们都是合数。

6.  证明：级数发散，此处使用了定理1注2中的记号。