最大公因数,最小公倍数 | 玄数

2012-03-10

1.  最大公因数

给定两个整数a、b,必有公共的因数,叫做公因数(Common Factor)。其中最大的一个叫做 a、b的最大公因数,记作a,b。如:

  • 12和48的公因数有:2、4、6、12,其中12最大,所以(12,48)= 12
  • 100和150的公因数有:2、5、10、25,其中25最大,所以(100,150)= 25

 

(1)如果a、b的最大公因数是1,称a、b互素。 如:

  • 3与7,19与39,100与101;
  • 所有的素数都互素

 

(2)如果 a | b,则(a,b)= a。 如:

  • 4 | 8,(4,8)= 4;
  • 10 | 20,(10,20)= 10;
  • 39 | 117,(39,117)= 39

 

(3)若a | bc,且(a,b)= 1,则 a | c。 如:

  • a = 3,b = 7,c = 6   ——  3 | 7×6,(3,7)= 1   →   3 | 6
  • a = 11,b = 17,c = 33   ——  11 | 17×33,(11,17)= 1   →   11 | 33
  • 7 = 3,b = 50,c = 49   ——  7 | 50×49,(7,50)= 1   →   7 | 49

 

(4)设a、b不同时为0,则存在一对整数m、n,使得(a,b)= am + bn。 如:

  • (12,48)= 12 = 2×3 + 1×6
  • (100,150)= 25 = 1×5 + 2×10
  • (39,117)= 39 = 2×7 + 5×5

 

 

2.   辗转相除法

当所给出的两个数很大时,如何求最大公因数?如(1012,374)= ?先看以下的准则,有助于理解:

若 a | bc+d,且a | b,则 a | d。 如:

  • 2 | 8×3+4,2 | 8   →   2 | 4
  • 5 | 10×7+35,5 | 10   →   5 | 35

 

证:                          a | b,设 b = aq

.                                 ∴   bc+d = acq + d

.                                 ∵   a | bc+d,即 a | acq +d

.                                        设 acq +d = at,t 是整数

.                                        则 d = at – acq = a (t – cq),t – cq 也是整数

.                                 ∴   a | d

 

设(1012,374)= x,1012 = 374×2 + 264,若x可以整除1012与374, 则x也可以整除264

.                                 ∴  (1012,374)=(374,264)

.                                         374 = 264 + 110

.                                 ∴  (374,264)=(264,110)

.                                         264 = 110×2+44

.                                 ∴  (264,110)=(110,44)

.                                         (110,44)= 22

.                                 ∴  (1012,374)=(374,264)=(264,110)=(110,44)= 22

 

 

设a、b为任意两个整数,且 b≠0

.                                        a = bq1 + r1         (a,b)=(b,r1

.                                         b = r1q2 + r2         (b,r1)=(r1,r2

.                                         r1 = r2q3 + r3         (r1,r2)=(r2,r3

.                                        ……

.                                         rn–2 = rn–1qn + rn      (rn–2,rn–1)=(rn–1,rn

.                                        rn–1 = rnqn+1         (rn–1,rn)=(rn,0)= rn

 

∴  (a,b)=(b,r1)=(r1,r2)=(r2,r3)…… =(rn–1,rn)=(rn,0)= rn

 

 

3.  最小公倍数

给定两个整数a、b,一定存在多个整数,它们同时为a、b的倍数,叫做a、b的公倍数(Common Multiple)。其中最小的一个叫做a、b的最小公倍数,记作[a,b]

如:4和6的公倍数有:12、24、36、48、60 … … 其中12最小,所以 [4,6] = 12

12和20的公倍数有:60、120、180、240 … … 其中60最小,所以 [12,20] = 60

 

若两个数互素,则它们的乘积就是它们的最小公倍数。如:[3,7] = 21,[11,17] = 187

 

 

4.  最大公因数与最小公倍数的关系:(a,b)[a,b] = | ab |。

即:a、b的最小公倍数 × a、b的最大公因数 = ab的绝对值。如:

(4,6)= 2,[4,6] = 12, (4,6)[4,6] = 24 = 4×6

(12,48)= 12,[12,48] = 48,  (12,48)[12,48] =12×48

 

 

5.   算术基本定理

任何大于1的整数总可以分解成素因素乘积的形式,并且,如果不计分解式中素因数的次序,这种分解式是唯一的。在实际应用中,常常将素因数分解式中相同的因素的乘机写成幂的形式。如:

48 = 2 × 2 × 2 × 2 × 3 = 24 × 3

100 = 2 × 2 × 5 × 5 = 22 × 52

1001 = 7 × 11 × 13

最大公因数,最小公倍数

上一篇

下一篇