初等数论教案(8)

1、第二节 最大公因数与辗转相除法第三节 最小公倍数教学目的：1、掌握最大公因数与最小公倍数性质；2、掌握辗转相除法；3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质教学难点：辗转相除法教学课时：6课时教学过程一、最大公因数1、定义1 整数a1, a2, L, ak的公共约数称为a1, a2, L, ak的公约数.不全为零的整数a1, a2, L, ak的公约数中最大的一个叫做a1, a2, L, ak的最大公约数（或最大公因数），记为(a1, a2, L, ak).注：1、由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数.2、如果(a1, a2, L

2、, ak) = 1，则称a1, a2, L, ak是互素的（或互质的）；如果(ai, a j) = 1，1 £ i, j £ k，i ¹ j，则称a1, a2, L, ak是两两互素的（或两两互质的）.显然，a1, a2, L, ak两两互素可以推出(a1, a2, L, ak) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2.2、定理1 下面的等式成立：() (a1, a2, L, ak) = (|a1|, |a2|, L, |ak|)；() (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|；() (a, b

3、) = (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). 证毕3、定理2 设a1, a2, L, akÎZ，记A = y；y =，xiÎZ，

4、1 £ i £ k .如果y0是集合A中最小的正数，则y0 = (a1, a2, L, ak).证明 设d是a1, a2, L, ak的一个公约数，则d½y0，所以d £ y0.另一方面，由第一节例2知，y0也是a1, a2, L, ak的公约数. 因此y0是a1, a2, L, ak的公约数中的最大者，即y0 = ( a1, a2, L, ak). 证毕推论1 设d是a1, a2, L, ak的一个公约数，则d½(a1, a2, L, ak).注：这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍

5、数.推论2 (ma1, ma2, L, mak) = |m|(a1, a2, L, ak).推论3 记d = (a1, a2, L, ak)，则= 1，特别地, = 1.4、定理3 (a1, a2, L, ak) = 1的充要条件是存在整数x1, x2, L, xk，使得a1x1 + a2x2 + L + akxk = 1. (1)证明 必要性 由定理2得到.充分性 若式(1)成立，如果 (a1, a2, L, ak) = d > 1，那么由d½ai（1 £ i £ k）推出d½a1x1 + a2x2 + L + akxk = 1，这是不可能的.

6、所以有(a1, a2, L, ak) = 1. 证毕5、定理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&

7、#189;bc，再由式(2)得到ab½c. 结论()得证. 证毕推论1 若 (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). 证毕推论2 若 (a, bi) = 1，1 £ i £ n，则(a, b1b2Lbn) = 1.证明 留作习题.6、定理5 对于任意的n个整数a1, a2,

8、 L, an，记(a1, a2) = d2，(d2, a3) = d3，L，(dn - 2, an - 1) = dn - 1，(dn - 1, an) = dn，则dn = (a1, a2, L, an).证明 由定理2的推论，我们有 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 = (

9、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，由定理2的推论及d2, L, dn的定义，依次得出 d½a1，d½a2 

10、22; 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 证明：若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(

11、x -ay) = (x -ay, (ab + 1)y - bx)，因此，是既约分数.例2 证明：121n2 + 2n + 12，nÎZ.解：由于121 = 112，n2 + 2n + 12 = (n + 1)2 + 11，所以，若112½(n + 1)2 + 11， (3)则11½(n + 1)2，因此，由定理4的推论1得到11½n + 1，112½(n + 1)2.再由式(3)得到112½11，这是不可能的.所以式(3)不能成立.注：这个例题的一般形式是：设p是素数，a，b是整数，则pk(an + b)k + pk - 1c，其中c

12、是不被p整除的任意整数，k是任意的大于1的整数.例3 设a，b是整数，且9½a2 + ab + b2， (4)则3½(a, b).解：由式(4)得到9½(a - b)2 + 3ab Þ 3½(a - b)2 + 3abÞ 3½(a - b)2 Þ 3½a - b (5)Þ 9½(a - b)2.再由式(4)得到9½3ab Þ 3½ab.因此，由定理4的推论1，得到3½a或3½b.若3½a，由式(5)得到3½b；若3&

13、#189;b，由(5)式也得到3½a.因此，总有3½a且3½b.由定理2的推论推出3½(a, b).例4 设a和b是正整数，b > 2，则2b - 12a + 1.解：() 若a < b，且2b - 1½2a + 1. (6)成立，则2b - 1 £ 2a + 1 Þ 2b - 2a £ 2 Þ 2a(2b - a - 1) £ 2，于是a = 1，b - a = 1，即b = 2，这是不可能的，所以式(6)不成立.() 若a = b，且式(6)成立，则由式(6)得到2a - 1&#

14、189;(2a - 1) + 2 Þ 2a - 1½2 Þ 2a - 1 £ 2 Þ 2a £ 3，于是b = a = 1，这是不可能的，所以式(6)不成立.() 若a > b，记a = kb + r，0 £ r < b，此时2kb - 1 = (2b - 1)(2(k - 1)b + 2(k - 2)b + L + 1) = (2b - 1)Q，其中Q是整数.所以2a + 1 = 2kb + r + 1 = 2r(2kb - 1 + 1) + 1 = 2r(2b - 1)Q + 1) + 1 = (2b - 1

15、)Q ¢ + (2r + 1)，其中Q¢是整数.因此2b - 1½2a + 1 Þ 2b - 1½2r + 1，在()中已经证明这是不可能的，所以式(6)不能成立.综上证得2b - 12a + 1.二、最小公倍数1、定义1 整数a1, a2, L, ak的公共倍数称为a1, a2, L, ak的公倍数. a1, a2, L, ak的正公倍数中的最小的一个叫做a1, a2, L, ak的最小公倍数，记为a1, a2, L, ak.2、定理1 下面的等式成立：() a, 1 = |a|，a, a = |a|；() a, b = b, a；() a1

16、, a2, L, ak = |a1|, |a2| L, |ak|；() 若a½b，则a, b = |b|.证明 留作习题.由定理1中的结论()可知，在讨论a1, a2, L, ak的最小公倍数时，不妨假定它们都是正整数. 在本节中总是维持这一假定.最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理.3、定理2 对任意的正整数a，b，有a, b =.证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此ak1 = bk2 . (1)于是.由于= 1，所以，其中t是某个整数. 将上式代入式(1)得到m =t . (2)另一方面，对于任意的

17、整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数.当t = 1时，得到最小公倍数a, b =.推论1 两个整数的任何公倍数可以被它们的最小公倍数整除.证明 由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2 设m，a，b是正整数，则ma, mb = ma, b.证明 由定理2及前面的定理2的推论得到ma, mb = ma, b.证毕4、定理3 对于任意的n个整数a1, a2, L, an，记a1, a2 = m2，m2, a3 = m3，L，mn-2, an-1 = mn-1，mn-1,

18、 an = mn，则a1, a2, L, an = mn.证明：我们有 mn = mn-1, an Þ mn-1½mn，an½mn，mn-1 = mn-2, an-1 Þ mn-2½mn-1½mn，an½mn，an-1½mn-1½mn，mn-2 = mn-3, an-2 Þ mn-3½mn-2½mn，an½mn，an-1½mn，an-2½mn，L L m2 = a1, a2 Þ an½mn，L，a2½mn，a1

19、89;mn，即mn是a1, a2, L, an的一个公倍数.另一方面，对于a1, a2, L, an的任何公倍数m，由定理2的推论及m2, L, mn的定义，得m2½m，m3½m，L，mn½m.即mn是a1, a2, L, an最小的正的公倍数. 证毕推论 若m是整数a1, a2, L, an的公倍数，则a1, a2, L, an½m .证明：留作习题.定理4 整数a1, a2, L, an两两互素，即(ai, aj) = 1，1 £ i, j £ n，i ¹ j的充要条件是a1, a2, L, an = a1a2Lan .

20、 (3)证明：必要性 因为(a1, a2) = 1，由定理2得到a1, a2 = a1a2 .由(a1, a3) = (a2, a3) = 1及前面的定理4推论得到(a1a2, a3) = 1，由此及定理3得到a1, a2, a3 = a1, a2, a3 = a1a2, a3 = a1a2a3 .如此继续下去，就得到式(3).充分性 用归纳法证明. 当n = 2时，式(3)成为a1, a2 = a1a2. 由定理2a1a2 = a1, a2 =Þ (a1, a2) = 1，即当n = 2时，充分性成立.假设充分性当n = k时成立，即a1, a2, L, ak = a1a2Lak

21、Þ (ai, aj) = 1，1 £ i, j £ k，i ¹ j.对于整数a1, a2, L, ak, ak + 1，使用定理3中的记号，由定理3可知a1, a2, L, ak, ak + 1 = mk, ak + 1. (4)其中mk = a1, a2, L, ak.因此，如果a1, a2, L, ak, ak + 1 = a1a2Lakak + 1，那么，由此及式(4)得到a1, a2, L, ak, ak + 1 = mk, ak + 1 = a1a2Lakak + 1，即= a1a2Lak ，显然mk £ a1a2Lak，(mk, a

22、k + 1) ³ 1.所以若使上式成立，必是(mk, ak + 1) = 1， (5)并且mk = a1a2Lak . (6)由式(6)与式(5)推出(ai, ak + 1) = 1，1 £ i £ k； (7)由式(6)及归纳假设推出(ai, aj) = 1，1 £ i, j £ k，i ¹ j . (8)综合式(7)与式(8)，可知当n = k + 1时，充分性成立. 由归纳法证明了充分性. 证毕定理4有许多应用. 例如，如果m1, m2, L, mk是两两互素的整数，那么，要证明m = m1m2Lmk整除某个整数Q，只需证明对于

23、每个i，1 £ i £ k，都有mi½Q. 这一点在实际计算中是很有用的. 对于函数f(x)，要验证命题“m½f(n)，nÎZ”是否成立，可以用第二节例5中的方法，验证“m½f(r)，r = 0, 1, L, m - 1”是否成立. 这需要做m次除法. 但是，若分别验证“mi½f(ri)，ri = 0, 1, L, mi - 1，1 £ i £ k”是否成立，则总共需要做m1 + m2 + L + mk次除法. 后者的运算次数显然少于前者.例1 设a，b，c是正整数，证明：a, b, c(ab, bc,

24、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 对于任意的整数a1, a2, L, an及整数k，1 £ k £ n，证明：a1, a2, L, an = a1, L, ak,ak + 1, L, an.解：因为a1, a2, L, an是a1, L, ak, ak + 1, L, an的公倍数，所以由定理2推论，推出a1, L, ak½a1, a2

25、, L, an，ak + 1, L, an½a1, a2, L, an，再由定理3推论知a1, L, ak, ak + 1, L, an½a1, a2, L, an. (11)另一方面，对于任意的ai（1 £ i £ n），显然ai½a1, L, ak, ak + 1, L, an，所以由定理3推论可知a1, a2, L, an½a1, L, ak, ak + 1, L, an，联合上式与式(11)得证.例3 设a，b，c是正整数，证明：a, b, cab, bc, ca = a, bb, cc, a.解：由定理2推论2及例2，有a,

26、 b, cab, bc, ca = a, b, cab, a, b, cbc, a, b, cca= a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac2= a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac2= abc, a2b, a2c, b2c, b2a, c2a, c2b以及a, bb, cc, a = a, bb, a, bcc, a= ab, b2, ac, bcc, a= abc, a, b2c, a, acc, a, bcc, a= abc, a2b, b2c, b2a, ac2, a2c, bc2, bca=

27、 abc, a2b, a2c, b2c, b2a, c2a, c2b，由此得证.三、辗转相除法本节要介绍一个计算最大公约数的算法辗转相除法，又称Euclid算法.它是数论中的一个重要方法，在其他数学分支中也有广泛的应用.1、定义1 下面的一组带余数除法，称为辗转相除法.设a和b是整数，b ¹ 0，依次做带余数除法： a = bq1 + r1， 0 < r1 < |b|， b = r1q2 + r2， 0 < r2 < r1 ，L L rk - 1 = rkqk + 1 + rk + 1，0 < rk + 1 < rk ， (1)L L rn - 2

28、 = rn - 1qn + rn， 0 < rn < rn-1 ， rn - 1 = rnqn + 1 .由于b是固定的，而且|b| > r1 > r2 > L ，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理1 用下面的方式定义Fibonacci数列Fn：F1 = F2 = 1，Fn = Fn - 1 + Fn - 2，n ³ 3，那么对于任意的整数n ³ 3，有Fn > a n - 2， (2)其中a =.证明：容易验证a 2 = a + 1.当n = 3时，由F3

29、 = 2 >= a可知式(2)成立.假设式(2)对于所有的整数k £ n（n ³ 3）成立，即Fk > a k - 2，k £ n，则Fn + 1 = Fn + Fn - 1 > a n - 2 + a n - 3 = a n - 3(a + 1) = a n - 3a 2 = a n- 1，即当k = n + 1时式(2)也成立.由归纳法知式(2)对一切n ³ 3成立.证毕.3、定理1(Lame) 设a, bÎN，a > b，使用在式(1)中的记号，则n < 5log10b.证明：在式(1)中，rn ³

30、 1，qn + 1 ³ 2，qi ³ 1（1 £ i £ n），因此rn ³ 1 = F2 ，rn - 1 ³ 2rn ³ 2 = F3 ，rn - 2 ³ rn - 1 + rn ³ F3 + F2 = F4 ，L Lb ³ r1 + r2 ³ Fn + 1 + Fn = Fn + 2 ，由此及式(2)得b ³ an =，即log10b ³ nlog10，这就是定理结论. 证毕4、定理2 使用式(1)中的记号，记P0 = 1，P1 = q1，Pk = qkPk -

31、 1 + Pk - 2，k ³ 2，Q0 = 0，Q1 = 1，Qk = qkQk - 1 + Qk - 2，k ³ 2，则aQk - bPk = (-1)k - 1rk，k = 1, 2, L, n . (3)证明：当k = 1时，式(3)成立.当k = 2时，有Q2 = q2Q1 + Q0 = q2，P2 = q2P1 + P0 = q2q1 + 1，此时由式(1)得到aQ2 - bP2 = aq2 - b(q2q1 + 1) = (a - bq1)q2 - b = r1q2 - b = -r2，即式(3)成立.假设对于k < m（1 £ m £

32、; n）式(3)成立，由此假设及式(1)得到 aQm - bPm= a(qmQm - 1 + Qm - 2) - b(qmPm - 1 + Pm - 2)= (aQm - 1 - bPm - 1)qm + (aQm - 2 - bPm - 2)= (-1)m - 2rm - 1qm + (-1)m - 3rm - 2= (-1)m - 1(rm - 2 - rm - 1qm) = (-1)m- 1rm ，即式(3)当k = m时也成立.定理由归纳法得证. 证毕5、定理3 使用式(1)中的记号，有rn = (a, b).证明：由第三节定理1，从式(1)可见rn = (rn - 1, rn) = (rn - 2, rn - 1) = L = (r1, r2) = (b, r1) = (a, b).证毕.现在我们已经知道，利用辗转相除法可以求出整数x，y，使得ax + by = (a, b) . (4)为此所需要的除法次数是O(log10b).但是如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些.例1 设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a, b).解：下面的四个基本事实给出了证明：() 若a½b，则(a, b) = a；() 若a = 2aa1，a ³ b ³ 1，则(a