最大公因數和最少公倍數

四．最大公因數和最小公倍數

這好比一條公路上兩端的兩個車站，一在東，一在西，看起來是多麼相同　 ----- 它們都同樣說整除，只不過一個是說整除別人，另一個是說被別人整除，方向相反的。而兩者計算的方法又多麼相似 ----- 同一條路上的景色就是這樣的，我讀書時，就迷失了方向，後來將這兩種數互相比併，才弄得一清二楚，不致混淆。

H.C.F.

L.C.M.

意義

公因數或者可以說是公除數，它整除題目所給的已知數，例如18和24

(2) |24 (2) |24

(3) |18 (3) |24

(6) |24 (6) |24

　　2整除18和24，所以2是18和24的公因數。

　　同樣，3和6也是18和24的公因數。

公倍數或者可以說是公被除數，它被題目所給的已知數整除，例如18和24

18 |(72) 24 |(72)

18 |(144) 24 |(144)

18 |(216) 24 |(216)

72被18和24整除，所以72是18和24的公倍數。

　　同樣，144和216也是18和24的公倍數。

公因數的個數是有限的，上題只有2, 3, 6三個，其中最有用的是最大的一個，叫做最大公因數。

簡寫做H.C.F.

上題記法：

18, 24 的H.C.F. = 6

華羅庚提出的記法是

| 18,24 | = 6

公倍數是無限的，將72乘以2，乘以3……可以得到無個數，其中最有用的是最小的一個，叫做最小公倍數。

簡寫做L.C.M.

上題記法：

18,24的L.C.M. = 72

華羅庚提出的記法是

{18,24} = 72

計算法

列舉法

18,24 的H.C.F. = ?

18,24的 L.C.M. = ?

18 = 1 x 18

= 2 x 9

= 3 x 6

24 = 1 x 24

= 2 x 12

= 3 x 8

= 4 x 6

18 x 1 = 18

18 x 2 = 36

18 x 3 = 54

18 x 4 = 72

18 x 5 = 90

24 x 1 = 24

24 x 2 = 48

24 x 3 = 72

24 x 4 = 96

18的因數是：2, 3, 6, 9, 18

24的因數是：2, 3, 4, 6, 8, 12, 24

相同的因數是2, 3, 6

最大的一個是6

18的倍數是：18, 36, 54, 72, 90…

24的倍數是：24, 48, 72, 96…

相同的公倍數是72…

最小的一個是72

指數法

將18, 24分解做質因數連乘式

2 | 18

3 | 9

   3

2 | 24

2 | 12

2 | 6

    3

2 | 24

2 | 12

2 | 6

3

2 | 18

3 | 9

3

18 = 2 x 3²

24 = 2³ x 3

18 = 2 x 3²

24 = 2³ x 3

方法：

1 同底的數，揀取指數最小的一份

2和2³，揀取2

3²和3，揀取3

18,24的H.C.F.

= 2 x 3

= 6

方法：

1 同底的數，揀取指數最大的一份

2和2³，揀取2³

3²和3，揀取3²

18,24的L.C.M.

= 2³ x 3²

= 8 x 9

= 72

2 沒有同底的數不要

例如：

A = 2 x 3⁴ x 5

B = 2³ x 3 x 7

A,B的H.C.F.= 2 x 3

2 沒有同底的數全要

例如：

A = 2 x 3⁴ x 5

B = 2³ x 3 x 7

A,B的L.C.M.= 2³ x 3⁴ x 5 x 7

短除法

2 | 18 24

3 | 9 12

3 4

18,24的H.C.F.

= 2 x 3

= 6

H.C.F.的H左邊是一直線，像提示將左邊直行的數乘起來就是答案

上題好像吃東西，咬大啖一些，沒有問題的

6 | 18 24

3 4

18,24的H.C.F.= 6

2 | 18 24

3 | 9 12

3 4

18,24的L.C.M.

= 2 x 3 x 3 x 4

= 72

L.C.M.的L，很象形地提示將直横行的數都乘起來就是答案

上題用大一些的數去除會快一些

6 | 18 24

3 4

18,24的L.C.M.

= 6 x 3 x 4

= 72　

如果計算三個數（或以上）的H.C.F.必須每個數都能整除，才可以去除

例：求12,18,45的H.C.F.

3 | 12 18 45

4 6 15

12,18,45的H.C.F. = 3

如果計算三個數（或以上）的L.C.M.，只要有兩個數能夠整除，便可以去除，沒有除的數照抄在下一行。

例：求12,18,45的L.C.M.

3 | 12 18 45

2 | 4 6 15

3 |2 3 15

2 1 5

12,18,45的L.C.M.

= 3 x 2 x 3 x 2 x 1 x 5

= 180

計算H.C.F.只做了一行便算完，但計算L.C.M.卻還可計下去。

在全部各數都可被整除的情況下，可用較大的數去除，令計算快些，但只整除兩數的情況下，用大數去除是不當的，上例：

6 | 12 18 45

3 | 2 3 45

2 1 15

12,18,45的L.C.M.

= 6 x 3 x 2 x 1 x 15

= 540 是錯的

當兩個數沒有數可以同時整除它們時，就說這兩個數是「互質數」，或者說它們的H.C.F. = 1

當兩個數沒有數可以同時整除它們時，它們的L.C.M.就是這兩數的乘積

例：1 | 5 9

5 9

5,9的H.C.F. = 1

例：1 | 5 9

5 9

5,9的L.C.M.

捷算法

當兩數有整除的情況，消去大數

例如求18,36的H.C.F.

18可整除36

消去大數36

餘下18就是答案

當兩數有整除的情況，消去細數

例如求18,36的L.C.M.

18可整除36

消去細數

餘下36是答案

最大公因數通常數字都是較小的，要消大數是容易記得的。

最小公倍數通常數字都是較大的，當然要消去的一定是細數。

例：求8,16,24的H.C.F.

8整除16，消去16

8整除24，消去24

所以8,16,24的H.C.F. = 8

例：8,16,24的L.C.M.

8整除16，消去8

餘下16和24

雖然未能一下得到答案，但將題目數字簡化為兩個數也易計一些。

如果數目簡單，也可以心算的。

如果數目不太大，也可以心算算出結果。

例如：求12,18的H.C.F.

12未能整除18

將細數得6，可整除18,

6就是12,18的H.C.F.

例如：求12,18的L.C.M.

12未能將18整除

將大數得36，可被12整除

36就是12,18的L.C.M.

如果未有結果，就，...一直找下去。

如果18 x 2未有結果，就12 x 3 , 12 x 4...一直找下去。

例如

求6,8的H.C.F.

這時2可除盡8

2就是它們的H.C.F.

例如

6,8的L.C.M.

8 x 2 = 16

8 x 3 = 24

這時24可給6除盡

24就是它們的L.C.M.

基本文字題

56,72都可被某數整除，某數最大是多少？

某數是56,72的H.C.F.

= 8

型式是：A,B的H.C.F.

某數都可被56和72整除，某數最小是多少？

某數是56,72的L.C.M.

= 504

型式是：A,B的L.C.M.

以某數除56餘6，以某數除72餘2，某數最大是多少？

某數是 ( 56 - 6 ), ( 72 – 2 )的H.C.F.

= 50,70的H.C.F.

= 10

型式是：(A-m),(B-n) 的H.C.F.

某數被56和72去除都餘1，某數最小是多少？

某數是56,72 的L.C.M.+1

= 504 + 1

= 505

型式是：A,B的L.C.M. + n

以某數除56欠9，以某數除72欠6，某數最大是多少？

某數是 (56 + 9 ) , ( 72 + 6 ) 的H.C.F.

= 65,78的H.C.F.

= 13

型式是：(A+m),(B+n)的H.C.F.

某數被56除餘54，某數被72除餘70，某數最小是多少？

（題目中的餘數，都是相同欠之才能整除）

某數是56,72的L.C.M.-2

型式是：A,B的 L.C.M.-n

以某數除56多1，以某數除72欠5，某數是最大是多少？

某數是 (56 – 1 ) , ( 72 + 5 ) 的H.C.F.

= 55,77的H.C.F.

= 11

型式是(A+m),(B-n)的H.C.F.

L.C.M.的文字題一般是上述三種：同時整除，相同餘數，相同欠數，如果隨便餘數或欠數，就不能用上述的L.C.M.去計算了。

例如：某數被4除餘3，被7除餘2，某數最小是多少？

這題既不同餘，又不同欠，計法是

3 (x 21) + 2 (x 8) = 79

79不是最小的答案，調整後最小的答案是23。

上式的21和8是從那兒來的？

題目的除數是4和7，就要這樣尋找

4的倍數，但用7除餘1，8就是，

7的倍數，但用4除餘1，21就是。

解決這4,7問題的關鍵數就是8和21。

試看看 8 + 21有什麼特性：

8 + 21

= 7 + 1 + 7 x 3 = 7倍數 + 1

8 + 21

= 4 x 2 + 4 x 5 + 1 = 4的倍數 + 1

　　現在要4除餘3，就將3乘到21去

8 + 21 x 3

= 8 + (20 + 1) x 3

= 8 + 20 x 3 + 3

= 4的倍數 + 3

　　現在要7除餘2，就將2乘到8去

8 x 2 + 21 x 3

= (7 + 1) x 2 + 21 x 3

= 7 x 2 + 2 + 21 x 3

= 7的倍數 +2

4和7做除數的問題，不論餘數是多少，都可按照下列公式去推算：

　　（4的餘數x21）＋（7的餘數x8）

文字方塊: 　　此類問題最經典最著名的是三五七問題，古書又稱做韓信點兵，鬼谷算，隔牆算，物不知總等名稱。

例如：某數被3除餘2，被5除餘1，被7除餘4，某數最小是多少？

公式是：

某數　= 3的餘數x70 + 5的餘數x21 + 7的餘數x15

= 2 x 70 + 1 x 21 + 4 x 15

= 221

　　調整後得最小的答案是11。

　　3,5,7問題的解決，關鍵就在70,21,15這三個數，它的來源是：

70是5、7的倍數，給3除則餘1，

21是3、7的倍數，給5除則餘1，

15是3、5的倍數，給7除則餘1，

計算的原理和上述的4、7問題相同。

古人為了記住這3,5,7問題的計算公式，就有這樣一首詩：

三人同行七十稀，

五樹梅花廿一枝，

七子團圓正半月，

除百零五便得知。

　　末句「除百零五」不是除，是減的意思，百零五是3 x 5 x 7 = 105，也是3,5,7的L.C.M.，上例中首先計得答案是221，不是最小，就連續減去105，直至得到最小的答案。

　　嚴格來說，這105並不一定用作減，如果題目要求答案是在500至600之間，那時就要加105，直至合需要為止。

　　還有類似的一首古詩，寫得隱晦一些：

三歲孩兒七十稀，

五留廿一事尤奇，

七度上元重相會，

寒食清明便可知。

　　詩中的上元，是正月十五，是十五的意思，而末句寒食清明又怎隱喻105呢？

　　寒食節有說在清明前一日，亦有說在清明前3日，古代都已弄得不很清楚，但通常合稱泛指清明節。原來每年冬至日至明年清明節，剛剛好105天，這些日期如果看農曆，是很難捉摸，反而看陽曆，卻很明確清楚的，每年冬至都是陽曆12月22日或23日，105日後的清明節亦一定在陽曆4月4日或5日。

　　冬至和清明，都是我國24節氣中的兩個節日，其他節氣日，若用陽曆去看，相信日期也很固定。

返回上述的短除法，有些性質也很有趣的，就下面這式子為例：

7 | 35 56

5 8

1). 35,56的 L.C.M. = 7 x 5 x 8 = 280

原來數字56就是7 x 8，35就是 7 x 5, 所以改為 5 x 56 = 280或8 x 35 = 280這樣計算會簡化一些。

2).從上面的短除式亦可以看出一條美妙的定理：

　　即是說：(A,B的H.C.F.) x (A,B的L.C.M.) = A x B

　　再回顧上述的捷算法，6可整除12，就說6是6和12的H.C.F.，其實6和12是題目中的已知數，要尋找的H.C.F.是未知數，結果這個6兼有兩重身份，既是已知數，又是未知數。

　　最後介紹求H.C.F.的輾轉相除法。

　　它的原理很簡單：如果兩個數都是m的倍數，它們的差也是m的倍數。

　　即是m整除第一個數，m又整除第二個數，就一定會整除它們的差數

am – bm = (a – b) m

例如：求68和76的H.C.F.

H.C.F.是除盡68和76的，即是68和76都是H.C.F.的倍數

文字方塊: 1) 68 76
â â
2) 68 68+8
â â
3) 68 8
â â
4) 8+8+8+8+8
+8+8+8+4 8
â â
5) 4 8

1)　現在要找的數就是要除盡68和76的數

2)　將76分解為68 + 8

　　如果所求數整除第一個數68，又整除第二個數76，就一定會整除它們的差數8，所以問題改為要找一個數可以整除68,68和8

3)　簡化地說，要找一個數整除68和8

4)　將68分解做，現在就要找一個數整除8,8,8,8,8,8,8,8,4和8

5)　簡化地說就是要找一個數整除4和8，現在4可整除8，4就是所求的H.C.F.

文字方塊: 8 68 76 1
64 68
4 8 2
8
0 　上述過程，用另一形式寫出來，就是輾轉相除的算法

　　首先用68除76餘8　（左除右）

　　然後用8除68餘4　（右除左）

再用4除8，除盡　（左除右）

4就是68和76的H.C.F.了。