初等数论书稿.doc

第一章 整数理论第一节 整除与带余数除法定义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, L, n Þ m½a1q1 + a2q2 + L + anqn，此处qi∈Z（i = 1, 2, L, 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

分别考虑以下两种情形：(ⅰ) 若在r1, r2, L, r5中数0，1，2都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时a1 + a2 + a3 = 3(q1 + q2 + q3) + 3可以被3整除；(ⅱ) 若在r1, r2, L, 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 若是形如（x,y∈Z，a，b是两个不全为零的整数）的数中的最小正数，则 ∣证明：不全为， 在整数集合中存在正整数，因而有形如的最小正数由带余除法有则，由是中的最小整数知 ∴ ∣注：（1）设a1, a2, L, an为不全为零的整数，以y0表示集合A = { y|y ==a1x1 + L + anxn，xiÎZ，1 £ i £ n }中的最小正数，则对于任何yÎA，y0½y；特别地，y0½ai，1 £ i £ n。

证明留给学生自己）2）此类题目的证明方法具有一般性，通常是针对所给的“最小正数”的概念进行反证法思考与练习1.11、证明：m½ai Þ m½a1q1 + a2q2 + L + anqn， qi∈Zi = 1, 2, L, n2、证明：6︱n(n+1)(2n+1) n∈N3、设a1, a2, L, an为不全为零的整数，以y0表示集合A = { y|y ==a1x1 + L + anxn，xiÎZ，1 £ i £ n }中的最小正数，则对于任何yÎA，y0½y；特别地，y0½ai，1 £ i £ n第二节 最大公因数定义1 设a1, a2, L, an是n（n≥2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1, a2, L, an的一个公因数；其中最大的一个公因数叫做a1, a2, L, an的最大公因数记为(a1, a2, L, an)由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数若(a1, a2, L, an) = 1，则称a1, a2, L, an是互质的；若(ai, a j) = 1，1 £ i, j £ n，i ¹ j，则称a1, a2, L, an是两两互质的。

显然，a1, a2, L, an两两互质可以推出(a1, a2, L, an) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2我们容易得到如下结论：定理1 若a1, a2, L, an为任意n个不全为零的整数则：(1) a1, a2, L, an与|a1|, |a2|, L, |an|的公因数相同；(2) (a1, a2, L, an) = (|a1|, |a2|, L, |an|)由定理1可知，在讨论(a1, a2, L, an)时，不妨假设a1, a2, L, 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, L, an，记(a1, a2) = d2，(d2, a3) = d3，L，(dn - 2, an - 1) = dn - 1，(dn - 1, an) = dn，则：dn = (a1, a2, L, 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，L L d2 = (a1, a2) Þ dn½an，dn½an - 1，L，dn½a2，dn½a1，即dn是a1, a2, L, an的一个公因数另一方面，对于a1, a2, L, an的任何公因数d，由d2, L, dn的定义，依次得出 d½a1，d½a2 Þ d½d2， d½d2，d½a3 Þ d½d3，L Ld½dn - 1，d½an Þ d½dn，因此 dn是a1, a2, L, an的公约数中的最大者故 dn = (a1, a2, L, an)注：这个定理对最大公因数的性质做了更深的刻划：最大公因数不但是公因数中的最大的，而且是所有公因数的倍数。

例1 设a1, a2, L, an为不全为零的整数，以y0表示集合A = { y|y ==a1x1 + L + anxn，xiÎZ，1 £ i £ n }中的最小正数，则y0=（a1, a2, L, an）证明：由于y0是集合A中的最小正数，故设d是a1, a2, L, an的任意一个公因数，则d∣，所以d≤y0又由本章第1节思考与练思考与练习3知，y0½ai，1 £ i £ n，因此y0也是a1, a2, L, an的一个公因数故y0一定是a1, a2, L, an所有公因数中的最大正数由此即得：y0=（a1, a2, L, an）注：由于（a1, a2, L, an）是集合A = { y|y ==a1x1 + L + anxn，xiÎZ，1 £ i £ n }中的最小正数，由此题的证明过程直接得到如下结论：设不全为零的整数a1, a2, L, an的最大公因数是（a1, a2, L, an），则存在整数，使得=a1t1 + L + antn =（a1, a2, L, an）由此，我们容易得到如下定理：定理5 （裴蜀（Bézout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，t∈Z，使得 as + bt = (a, b) 。

推论5.1 (a, b)＝1的充要条件是：存在s，t∈Z，使得 as + bt = 1还可以推广为如下结论：推论5.2 (a1, a2, L, an) = 1的充要条件是：存在整数x1, x2, L, xn，使得a1x1 + a2x2 + L + anxn = 1 定理6 若a，b，c是任意的三个整数，且(a, c)＝1，则(1) ab，c与b，c有相同的公因数；(2) （ab，c）＝（b，c）上面假定了b，c至少有一个不为零证明：（1）由题设及推论5.1，存在s，t∈Z，使得 as + ct = 1两边乘以b，即得：(ab)s + c(bt) = b 设d是ab与c的任一公因数，由上式得：d︱b，因而d是b,c的一个公因数反之b,c的任一公因数显然是ab与c的一个公因数故第一部分获证2）因为b，c不全为零，所以（b,c）是存在的，于是由（1）知（ab，c）存在，且（ab，c）＝（b，c）推论6.1 若(a, c) = 1，c½ab，则c½b推论6.2 若 (a, bi) = 1，1 £ i £ n，则(a, b1b2Lbn) = 1推论6.3 若 (ai, bj) = 1，1 £ i£ n，1 £j£ m， 则 (a1a2Lan , b1b2Lbm) = 1特别地，若（a，b）=1，则（an，bm）=1。

例2 设a，b，c，n是正整数，ab = cn ，(a, b) = 1，则存在正整数u，v，使得a = un，b = vn，c = uv，(u, v) = 1证明：因为(a, b) = 1，所以(b, an-1)=1，于是 ；同理可得，令，则 a = un，b = vn，c = uv，且 故结论成立注：此题说明，若互质的两个正整数之积是一个整数的n次幂，则这两个正整数都是整数的n次幂此结论可以推广为：若两两互质的s个正整数之积是一个整数的n次幂，则这s个正整数都是整数的n次幂这个性质表现了整数互质的重要性，其应用较广泛思考与练习1.21、证明本节定理32、设m、n为正整数，m为奇数，。