初等数论书稿

第一章 整数理论

第一节 整除与带余数除法

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

a = bq

成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：b?a；如果不存在整数q使得a = bq成立，则称b不能整除a或a不被b整除，记作：b?|a。

定理1 下面的结论成立： (1) a?b，b?c ? a?c；（传递性） (2) m?a，m?b ? m?(a±b)

(3) m?ai，i = 1, 2, ?, n ? m?a1q1 ? a2q2 ? ? ? anqn，此处qi∈Z（i = 1, 2, ?, n）。 （证明留给学生自己） 注：① a?b ? ?a??b；

② b?a ? bc?ac，此处c是任意的非零整数； ③ b?a，a ? 0 ? |b| ? |a|； b?a且|a| < |b| ? a = 0。

④因式分解 an- bn=(a-b) M1, n∈Z an+bn=(a+b)M2, 2n M1，M2∈Z 定理2(带余数除法) 设a与b是两个整数，b >0，则存在唯一的两个整数q和r，使得 a = bq ? r，0 ? r < b。 (1)

此外，b?a的充要条件是r=0 证明 存在性 作整数序列：

…，-3b，-2b，-b，0，b，2b，3b，….

则a必在上述序列的某两项之间，即存在整数q，使得：qb? a <(q+1) b， 0? a- qb

唯一性 假设有两对整数q ?，r ?与q ??，r ??都使得式(1)成立，即

a = q ??b ? r ?? = q ?b ? r ?，0 ? r ?, r ?? < b，

1

则 (q?? ? q ?)b = r ? ? r ??，0 ?|r ? ? r ??| < b， (2) 因此，由b||r ? ? r ??|知，r ? ? r ?? = 0，r ? = r ??，再由式(2)得出q ? = q ?? 从而q和r是唯一的。

定义2 称式(1)中的q是a被b除的商，r是a被b除的余数。 例1 任意给出的五个整数中，必有三个数之和被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整除。

综合(ⅰ) 、(ⅱ)可知，所证结论成立。

注：此题利用了数学中的一个重要原理——抽屉原理，也称为P.G.Dirichlet原理，即把n+1个元素或更多的元素放入n个抽屉中，则在其中一个抽屉里至少要放入2个元素。值得注意的是，利用带余数除法得到的余数进行分类来构造抽屉是数论解题中常用的方法。

例2 若ax0?by0是形如ax?by（x,y∈Z，a，b是两个不全为零的整数）的数中的最小正数，则 ax0?by0∣ax?by

证明：?a,b不全为0，

?在整数集合S??ax?by|x,y?Z?中存在正整数，因而有形如ax?by的最小正数ax0?by0。?x,y?Z，由带余除法有ax?by?(ax0?by0)q?r,0?r?ax0?by0。则

r?(x?x0q)a?(y?y0q)b?S，由ax0?by0是S中的最小整数知 r?0

2

∴ ax0?by0∣ax?by

注：（1）设a1, a2, ?, an为不全为零的整数，以y0表示集合

A = { y|y =?aixi=a1x1 ? ? ? anxn，xi?Z，1 ? i ? n }

i?1n中的最小正数，则对于任何y?A，y0?y；特别地，y0?ai，1 ? i ? n。 （证明留给学生自己）。

（2）此类题目的证明方法具有一般性，通常是针对所给的“最小正数”的概念进行反证法。

思考与练习1.1

1、证明：m?ai ? m?a1q1 ? a2q2 ? ? ? anqn， qi∈Z。i = 1, 2, ?, n 2、证明：6︱n(n+1)(2n+1) n∈N。

3、设a1, a2, ?, an为不全为零的整数，以y0表示集合

A = { y|y =?aixi=a1x1 ? ? ? anxn，xi?Z，1 ? i ? n }

i?1n中的最小正数，则对于任何y?A，y0?y；特别地，y0?ai，1 ? i ? n。

第二节 最大公因数

定义1 设a1, a2, ?, an是n（n?2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1, a2, ?, an的一个公因数；其中最大的一个公因数叫做a1, a2, ?, an的最大公因数。记为(a1, a2, ?, an)。

由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。 若(a1, a2, ?, an) = 1，则称a1, a2, ?, an是互质的；若

(ai, a j) = 1，1 ? i, j ? n，i ? j，

则称a1, a2, ?, an是两两互质的。

3

显然，a1, a2, ?, an两两互质可以推出(a1, a2, ?, an) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2。

我们容易得到如下结论：

定理1 若a1, a2, ?, an为任意n个不全为零的整数。则： (1) a1, a2, ?, an与|a1|, |a2|, ?, |an|的公因数相同； (2) (a1, a2, ?, an) = (|a1|, |a2|, ?, |an|)。

由定理1可知，在讨论(a1, a2, ?, an)时，不妨假设a1, a2, ?, an是正整数，以后我们就维持这一假设。并且我们容易得到如下结论：

定理2 若b是任一整数，则：

(1) 0与b的公因数就是b的因数，反之，b的因数也就是0与b的公因数； (2) （0，b）= ︱b︱ 。

定理3 若a，b，c是任意三个不全为零的整数，且a =bq?c，其中q是非零整数，则a，b与b，c有相同的公因数，因而(a, b) = (b, c)。（证明留给学生自己）

定理4 对于任意的n个整数a1, a2, ?, an，记

(a1, a2) = d2，(d2, a3) = d3，?，(dn ? 2, an ? 1) = dn ? 1，(dn ? 1, an) = dn，

则：dn = (a1, a2, ?, an)。

证明：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 ? 2?dn ? 3

? dn?an，dn?an ? 1，dn?an ? 2，dn?dn ? 3，

? ?

d2 = (a1, a2) ? dn?an，dn?an ? 1，?，dn?a2，dn?a1，

即dn是a1, a2, ?, an的一个公因数。

另一方面，对于a1, a2, ?, an的任何公因数d，由d2, ?, dn的定义，依次得出

4