初等数论笔记.docVIP

PAGE

PAGE1

第一章整数理论

第一节整除与带余数除法

定义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整除，记作：ba。

定理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∈Zan+bn=(a+b)M2,2nM1，M2∈Z

定理2(带余数除法)设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bq?r，0?rb。(1)

此外，b?a的充要条件是r=0

证明存在性作整数序列：

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

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

成立，令a-qb=r，则a=bq+r，且0?rb。

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

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

则(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?ri3，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整除；

(ⅱ)若在r1,r2,?,r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1=r2=r3=r（r=0，1或2），此时

a1?a2?a3=3(q1?q2?q3)

可以被3整除。

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

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

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

证明：不全为，

在整数集合中存在正整数，因而有形如的最小正数。，由带余除法有。则，由是中的最小整数知

∴∣

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

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

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

（证明留给学生自己）。

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

思考与练习1.1

1、证明：m?ai?m?a1q1?a2q2???anqn，qi∈Z。i=1,2,?

2、证明：6︱n(n+1)(2n+1)n∈N。

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

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

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

第二节最大公因数

定义1设a1,a2,?,