初等数论教案1_初等数论教案

初等数论教案1由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“初等数论教案”。

第二节 最大公因数与辗转相除法

第三节 最小公倍数

教学目的：

1、掌握最大公因数与最小公倍数性质；

2、掌握辗转相除法；

3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质 教学难点：辗转相除法 教学课时：6课时 教学过程

一、最大公因数

1、定义

1整数a1, a2, , ak的公共约数称为a1, a2, , ak的公约数.不全为零的整数a1, a2, , ak的公约数中最大的一个叫做a1, a2, , ak的最大公约数（或最大公因数），记为(a1, a2, , ak).注：

1、由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数.2、如果(a1, a2, , ak)= 1，则称a1, a2, , ak是互素的（或互质的）；如果

(ai, a j)= 1，1  i, j  k，i  j，则称a1, a2, , ak是两两互素的（或两两互质的）.显然，a1, a2, , ak两两互素可以推出(a1, a2, , ak)= 1，反之则不然，例如(2, 6, 15)= 1，但(2, 6)= 2.2、定理

1下面的等式成立：(ⅰ)(a1, a2, , ak)=(|a1|, |a2|, , |ak|)；(ⅱ)(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).证毕

3、定理

2设a1, a2, , akZ，记

A = { y；y =aixi，xiZ，  i  k }.i1k如果y0是集合A中最小的正数，则y0 =(a1, a2, , ak).证明

设d是a1, a2, , ak的一个公约数，则dy0，所以d  y0.另一方面，由第一节例2知，y0也是a1, a2, , ak的公约数.因此y0是a1, a2, , ak的公约数中的最大者，即y0 =(a1, a2, , ak).证毕

推论

1设d是a1, a2, , ak的一个公约数，则d(a1, a2, , ak).注：这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数.推论2

(ma1, ma2, , mak)= |m|(a1, a2, , ak).推论

3记 =(a1, a2, , ak)，则

(aa1a2，,k)= 1，特别地,(ab,)= 1.(a,b)(a,b)

4、定理

3(a1, a2, , ak)= 1的充要条件是存在整数x1, x2, , xk，使得

a1x1  a2x2    akxk = 1.(1)证明

必要性

由定理2得到.充分性

若式(1)成立，如果(a1, a2, , ak)= d > 1，那么由dai（1  i  k）推出da1x1  a2x2    akxk = 1，这是不可能的.所以有(a1, a2, , 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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, b1b2bn)= 1.证明

留作习题.6、定理

5对于任意的n个整数a1, a2, , an，记

(a1, a2)= d2，(d2, a3)= d3，，(dn  2, an  1)= dn  1，(dn  1, an)= dn，则

dn =(a1, a2, , 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 =(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，由定理2的推论及d2, , dn的定义，依次得出

da1，da2  dd2，dd2，da3  dd3， 

ddn  1，dan  ddn，因此dn是a1, a2, , an的公约数中的最大者，即dn =(a1, a2, , an).例

1证明：若n是正整数，则21n414n3是既约分数.解：由定理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)，因此，xay(ab1)ybx是既约分数.例

2证明：121|n2  2n  12，nZ.解：由于121 = 112，n2  2n  12 =(n  1)2  11，所以，若

112(n  1)2  11，则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是不被p整除的任意整数，k是任意的大于1的整数.例

3设a，b是整数，且

9a2  ab  b2，则3(a, b).(3)

(4)

解：由式(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b，由(5)式也得到3a.因此，总有3a且3b.由定理2的推论推出3(a, b).例

4设a和b是正整数，b > 2，则2b  1|2a  1.解：(ⅰ)若a

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(2a  1) 2  2a  12  2a  1  2  2a  3，于是b = a = 1，这是不可能的，所以式(6)不成立.(ⅲ)若a > b，记a = kb  r，0  r

2kb  1 =(2b  1)(2(k  1)b  2(k  2)b    1)=(2b  1)Q，其中Q是整数.所以

2a  1 = 2kb + r  1 = 2r(2kb  1  1) 1 = 2r((2b  1)Q  1) 1 =(2b  1)Q  (2r  1)，其中Q是整数.因此

2b  12a  1  2b  12r  1，在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立.综上证得2b  1|2a  1.二、最小公倍数

1、定义

1整数a1, a2, , ak的公共倍数称为a1, a2, , ak的公倍数.a1, a2, , ak的正公倍数中的最小的一个叫做a1, a2, , ak的最小公倍数，记为[a1, a2, , ak].2、定理

1下面的等式成立：(ⅰ)[a, 1] = |a|，[a, a] = |a|；(ⅱ)[a, b] = [b, a]；

(ⅲ)[a1, a2, , ak] = [|a1|, |a2| , |ak|]；(ⅳ)若ab，则[a, b] = |b|.证明

留作习题.由定理1中的结论(ⅲ)可知，在讨论a1, a2, , ak的最小公倍数时，不妨假定它们都是正整数.在本节中总是维持这一假定.最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理.3、定理

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

[a, b] =

ab(a,b).证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此

ak1 = bk2.(1)于是

abk1k2.(a,b)(a,b)由于(ab,)= 1，所以(a,b)(a,b)b|k1，即k1bt(a,b)(a,b)，其中t是某个整数.将上式代入式(1)得到

m =

abt.(a,b)

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

[a, b] =

ab(a,b).推论

1两个整数的任何公倍数可以被它们的最小公倍数整除.证明

由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2

设m，a，b是正整数，则[ma, mb] = m[a, b].证明

由定理2及前面的定理2的推论得到

m2abm2abmab[ma, mb] == m[a, b].(ma,mb)m(a,b)(a,b)证毕

4、定理

3对于任意的n个整数a1, a2, , an，记

[a1, a2] = m2，[m2, a3] = m3，，[mn2, an1] = mn1，[mn1, an] = mn，则

[a1, a2, , 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， 

m2 = [a1, a2]  anmn，，a2mn，a1mn，即mn是a1, a2, , an的一个公倍数.另一方面，对于a1, a2, , an的任何公倍数m，由定理2的推论及m2, , mn的定义，得

m2m，m3m，，mnm.即mn是a1, a2, , an最小的正的公倍数.证毕

推论

若m是整数a1, a2, , an的公倍数，则[a1, a2, , an]m.证明：留作习题.定理

4整数a1, a2, , an两两互素，即

(ai, aj)= 1，1  i, j  n，i  j的充要条件是

[a1, a2, , an] = a1a2an.(3)证明：必要性

因为(a1, a2)= 1，由定理2得到

[a1, a2] =

a1a2(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.由定理2 a1a2 = [a1, a2] =即当n = 2时，充分性成立.假设充分性当n = k时成立，即

[a1, a2, , ak] = a1a2ak (ai, aj)= 1，1  i, j  k，i  j.对于整数a1, a2, , ak, ak + 1，使用定理3中的记号，由定理3可知

[a1, a2, , ak, ak + 1] = [mk, ak + 1].(4)其中mk = [a1, a2, , ak].因此，如果

[a1, a2, , ak, ak + 1] = a1a2akak + 1，那么，由此及式(4)得到

[a1, a2, , ak, ak + 1] = [mk, ak + 1] =即

mk(mk,ak1)mkak1(mk,ak1)a1a2(a1,a2)(a1, a2)= 1，= a1a2akak + 1，= a1a2ak，显然mk  a1a2ak，(mk, ak + 1) 1.所以若使上式成立，必是

(mk, ak + 1)= 1，(5)并且

mk = a1a2ak.(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, , mk是两两互素的整数，那么，要证明m = m1m2mk整除某个整数Q，只需证明对于每个i，1  i  k，都有miQ.这一点在实际计算中是很有用的.对于函数f(x)，要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，验证“mf(r)，r = 0, 1, , m  1”是否成立.这需要做m次除法.但是，若分别验证“mif(ri)，ri = 0, 1, , mi  1，1  i  k”是否成立，则总共需要做m1  m2    mk次除法.后者的运算次数显然少于前者.例

1设a，b，c是正整数，证明：[a, b, c](ab, bc, ca)= abc.解：由定理3和定理2有

[a, b, c] = [[a, b], c] =由第三节定理5和定理2的推论，(ab, bc, ca)=(ab,(bc, ca))=(ab, c(a, b))

=(ab,abc)(ab[a,b],abc)ab([a,b],c).[a,b][a,b][a,b][a,b]c，([a,b],c)

(9)

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

2对于任意的整数a1, a2, , an及整数k，1  k  n，证明：

[a1, a2, , an] = [[a1, , ak],[ak + 1, , an]].解：因为[a1, a2, , an]是a1, , ak, ak + 1, , an的公倍数，所以由定理2推论，推出

[a1, , ak][a1, a2, , an]，[ak + 1, , an][a1, a2, , an]，再由定理3推论知

[[a1, , ak], [ak + 1, , an]][a1, a2, , an].另一方面，对于任意的ai（1  i  n），显然

ai[[a1, , ak], [ak + 1, , an]]，所以由定理3推论可知

[a1, a2, , an][[a1, , ak], [ak + 1, , an]]，联合上式与式(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] = [[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] 以及

(11)

[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a] = [ab, b2, ac, bc][c, a] = [ab[c, a], b2[c, a], ac[c, a], bc[c, a]] = [abc, a2b, b2c, b2a, ac2, a2c, bc2, bca] = [abc, a2b, a2c, b2c, b2a, c2a, c2b]，由此得证.三、辗转相除法

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

1下面的一组带余数除法，称为辗转相除法.设a和b是整数，b  0，依次做带余数除法：

a = bq1  r1，0

b = r1q2  r2，0

 

rk  1 = rkqk + 1  rk + 1，0

(1)

 

rn  2 = rn  1qn  rn，0

rn  1 = rnqn + 1.由于b是固定的，而且

|b| > r1 > r2 > ，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理

1用下面的方式定义Fibonacci数列{Fn}：

F1 = F2 = 1，Fn = Fn  1  Fn  2，n  3，那么对于任意的整数n  3，有

Fn >  n  2，(2)其中 =152.证明：容易验证

 2 =   1.当n = 3时，由

F3 = 2 >1可知式(2)成立.假设式(2)对于所有的整数k  n（n  3）成立，即

Fk >  k  2，k  n，则

Fn + 1 = Fn  Fn  1 >  n  2   n  3 =  n  3(  1)=  n  3 2 =  n 1，即当k = n  1时式(2)也成立.由归纳法知式(2)对一切n  3成立.证毕.3、定理1(Lame)设a, bN，a > b，使用在式(1)中的记号，则

n

rn  1 = F2，rn  1  2rn  2 = F3，52=  rn  2  rn  1  rn  F3  F2 = F4， 

b  r1  r2  Fn + 1  Fn = Fn + 2，由此及式(2)得

b  n =(1即

log10b  nlog101这就是定理结论.证毕

4、定理

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

P0 = 1，P1 = q1，Pk = qkPk  1  Pk  2，k  2，Q0 = 0，Q1 = 1，Qk = qkQk  1  Qk  2，k  2，则

aQk  bPk =(1)k  1rk，k = 1, 2, , 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

aQm  bPm= a(qmQm  1  Qm  2) b(qmPm  1  Pm  2)

52)n，521n，5=(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)=  =(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 = 2a1，2|a1，b2b1，2|b1，    1，则

(a, b)= 2(2  a1, b1)；

(ⅲ)若2|a，b2b1，2|b1，则(a, b)=(a, b1)；

ab(ⅳ)若2|a，2|b，则(a,b)(||,b).2在实际计算过程中，若再灵活运用最大公约数的性质（例如第三节定理4的推论），则可使得求最大公约数的过程更为简单.例

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

125x  17y =(125, 17).解：做辗转相除法：

= 717  6，q1 = 7，r1 = 6，= 26  5，q2 = 2，r2 = 5，= 15  1，q3 = 1，r3 = 1，= 51，q4 = 5.由定理4，(125, 17)= r3 = 1.利用定理2计算（n = 3）

P0 = 1，P1 = 7，P2 = 27  1 = 15，P3 = 115  7 = 22，Q0 = 0，Q1 = 1，Q2 = 21  0 = 2，Q3 = 12  1 = 3，取x =(1)3  1Q3 = 3，y =(1)3P3 = 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(x  kn)= n(km  y)，这样，当k充分大时，总可找出正整数x0，y0，使得 mx0 = ny0.上式说明，如果放y0次（每次放n个），那么在使m个盒子中各放x0个后，还多出一个硬币.把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1.因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同.四、小结.五、作业

24页ex5、ex6、ex7、ex8、ex11 25页ex16 26页ex29、ex36