最大公因數與最小公倍數
共同的零件，足夠的零件。

01 · 學完馬上練

公因數：共同分得開，才算共同。

12的正因數是1、2、3、4、6、12；18的正因數是1、2、3、6、9、18。兩邊都有的1、2、3、6，就是12與18的公因數。

為什麼叫「最大」？因為6是在共同因數裡最大的。不是先挑最大的原數，也不是把兩數隨便相減。

02 · 學完馬上練

互質是兩個數的關係，不是兩個數的種類。

8的因數為1、2、4、8；15的因數為1、3、5、15。共同的只有1，因此8與15互質。兩個都是合數，仍然可以互質。

兩個相異質數一定互質；質數與合數則不一定，例如2和6不互質。連續兩個正整數一定互質：若某數d同時整除n與n+1，就能整除它們的差1，所以d只能是1。

注意「三數的最大公因數是1」與「三數兩兩互質」不同。6、10、15沒有三者共有的大於1因數，但6與10仍共有2，6與15共有3，10與15共有5。

1能和別的數互質嗎？

可以。1只有正因數1，所以gcd(1,n)=1，對任何正整數n都成立，包含n=1。這再一次說明互質描述的是關係，不是「兩個都是質數」。

03 · 學完馬上練

最大公因數為什麼取較小次方？

把數字當成零件清單。24=2³×3，36=2²×3²。如果某數是兩者的公因數，它每一種零件的數量都不能超過任一原數。

2最多拿兩個，因為36只有兩個2；3最多拿一個，因為24只有一個3。任何一種拿得更多，就不可能同時整除兩個原數；拿滿這些共同零件，才是最大的公因數。

短除法，把共同零件一次拿到外面。

剩下2與3互質，表示沒有大於1的共同零件可再提取。三數求最大公因數時，每一步必須能整除所有剩餘數。

質因數不只兩種，也逐個底數比較。

求最大公因數，先圈出兩式都有的質因數底數，再各取較小指數；求最小公倍數，則列出兩式出現過的所有底數，各取較大指數。少了一個質因數，就代表那個底數的指數是0；不是把整個數較小的那一式照抄。

互動 · 標準分解式逐項對照

改兩個數，對齊底數，再比較指數。

04 · 學完馬上練

數字大又接近：從更相減損術走到輾轉相除法。

先看為什麼「相減」不會改變共同因數。

若d同時整除a和b（a>b），設a=dm、b=dn，就有a−b=d(m−n)，因此d也整除差。反過來，若d整除b與a−b，它也整除兩者的和a。所以(a,b)和(b,a−b)的公因數完全相同，最大公因數也相同。

1050與1008很接近，先相減得42。因為1008=42×24，所以gcd(1050,1008)=gcd(1008,42)=42。這就是更相減損術的核心：反覆以大減小，直到兩數相等，相等的數就是最大公因數。相差很大時，逐次相減會比較慢。

跟著影片算：87 與 58。

1. 大減小：87−58＝29，問題改看58與29。
2. 再相減：58−29＝29，此時兩個數都是29。
3. 兩數相同便可停；若再減一次得到0，答案仍是29，不是0。
4. 代回驗算：87＝29×3，58＝29×2。

真正保留下來的是「整組公因數」，不只是某一個共同因數。正向：d同除a、b，就能除a−b；反向：d同除b、a−b，也能除它們的和a。兩邊都成立，才保證最大公因數沒有偷偷變大或變小。若一路算到1，便能判定原兩數互質；互質不要求原兩數都是質數。

一次減掉好幾個除數，就是取餘數。

若a=bq+r，任何a、b的公因數都整除r=a−bq；任何b、r的公因數也整除a=bq+r。所以gcd(a,b)=gcd(b,r)，這是輾轉相除法，不用先把大數分解成質因數。

餘數是0時要停，答案是最後的非零除數，不能拿0再當除數。兩數若相等，本身就是最大公因數；若最後非零數是1，原兩數互質。

從多次相減，壓縮成一次除法。

若a＝bq＋r，就代表從a連續減去q個b，最後剩r。例如30＝8×3＋6：30−8−8−8＝6；接著8＝6×1＋2，6＝2×3＋0，所以最大公因數是2。每一步改看「上一個除數與餘數」，不是改看商。

停止條件要說精確：相減法看到兩數相等即可停；相除法餘數為0時，取這一步的除數。餘數會小於除數，正整數不可能無限下降，所以過程一定會結束。

05 · 學完馬上練

看得見的公倍數：把兩列、三列的共同數找出來。

4的正倍數列是4、8、12、16、20、24……；6的正倍數列是6、12、18、24……。兩列共同出現的12、24、36……就是正公倍數，第一個是最小公倍數12。所有正公倍數就是12的正倍數。

若再加一列10、20、30、40、50、60……，第一個三列都有的數變成60。不能把「任意兩列有重合」當成「三列共同重合」。0也是公倍數，但我們求的是最小正公倍數，所以本模式從各數的第一個正倍數開始。

延伸到等差數列題庫：兩數列相遇 ↗

06 · 學完馬上練

最小公倍數為什麼反而要取較大次方？

24的正倍數有24、48、72……；36的正倍數有36、72、108……。72是第一次重合，所以是最小正公倍數。最小公倍數在此限定正的公倍數，不能把0拿來當答案。

共同倍數需要讓24與36都能整除它，零件就必須足以供應兩邊。2至少3個，3至少2個：

種類全部要，次數至少取較大的。再多加零件仍是公倍數，但就不是最小。互質的正整數沒有重複的質因數，最小公倍數就是兩數相乘。

07 · 學完馬上練

起點不同：先找第一次共同數，再看重合間隔。

兩列都每隔固定數往前，就是等差數列。現在先不用通項公式，直接列：A從1開始、每次加4，是1、5、9、13、17、21、25……；B從3開始、每次加6，是3、9、15、21、27……。第一次共同數是9，後面是21、33……，每隔12重合一次。

12是間隔4與6的最小公倍數，卻不是第一次共同數。先依起點找到第一次，再加12得到後續共同數。後面的6:00與6:05發車例題，也是同一個想法。

不是每兩列都一定相遇。

1、5、9、13……全部是奇數；2、8、14、20……全部是偶數，永遠不會有共同數。進一步看，若共同數x存在，x=a+pm=b+qn，所以b−a=pm−qn，必須是gcd(p,q)的倍數。在整數起點、正整數間隔的條件下，起點差能被兩間隔的最大公因數整除，也能保證往後找到共同數。

在這裡的互動試試(1,+4)與(3,+6)，再把第二個起點改成2，觀察結果。三列相遇時，三個條件都要同時滿足。

08 · 學完馬上練

三數短除法：沒有三者共有，不代表能停。

8、12、10同除2後，得到4、6、5。三者的最大公因數已是1，但求最小公倍數時還不能停，因為4與6仍重複含有2。

求最小公倍數的短除法，每一步選一個能整除至少兩數的質數，能除的除，不能除的照抄，直到剩下的數兩兩互質。若在4、6、5停下，把2×4×6×5相乘會得到240，多算了一個2。

09 · 學完馬上練

韓信點兵：同餘、同缺與不同餘數的三種類型。

先將每個排法翻成「除數、餘數」，再辨認是否能同時加上或減去一個數。以下三類都用3、5、7，最小公倍數L＝105；但第一個符合的人數不同。

第一類：同餘型——都多1個。

3個一數多1、5個一數多1、7個一數也多1。把多的1人移開，n−1就能同時被3、5、7整除。

若題目只問最小正整數，1也符合，因為商可以是0；若要求每種排法至少排出一整組，或人數大於7，最小才是106。先看題目範圍，再決定從哪一項開始。

第二類：同缺型（不足型）——都差2個才排滿。

除3餘1、除5餘3、除7餘5，看起來餘數不同，但分別距離下一個整倍數都是2。補上2人，n＋2就能同時被3、5、7整除。

驗算103：103＝3×34＋1＝5×20＋3＝7×14＋5。辨識不足型時，要算「除數−餘數」，不能只比較餘數。加2以後是共同倍數，最後別忘了減回2。

第三類：一般餘數型——先找第一次共同，再按間隔延伸。

除3餘1、除5餘2、除7餘3；餘數不全相同，距離排滿也分別差2、3、4，無法直接用同餘或同缺的捷徑。

代回52：52＝3×17＋1＝5×10＋2＝7×7＋3。找到第一項後，每加105都增加3、5、7的整倍數，因此餘數不變。反過來，若兩個數符合相同的三組餘數，它們的差必能被3、5、7整除，所以差必為105的倍數；這也說明不會漏掉中間的其他解。

例如要求200到400人：52＋105＝157太小，下一項262符合，再下一項367也符合；最後須依題目問「最少」還是「全部」作答。這三個除數互質，所以各種合法餘數都有解；一般自訂公差未必如此，例如除4餘1與除6餘2，一個要求奇數、一個要求偶數，就沒有共同解。

10 · 學完馬上練

應用題先列條件，不用關鍵字猜公式。

有24顆紅珠與36顆藍珠，要分成相同組合的小包，兩種都分完。若分成k包，每包紅珠24÷k、藍珠36÷k都必須是整數，所以k是公因數。最多分12包，每包2紅、3藍。

兩盞燈分別每12秒、18秒亮一次，現在同時亮。下一次同時亮的時間t必須同時是12與18的正倍數，所以最早在36秒後。

同餘、同缺的推理與練習，回看韓信點兵段落。

起點不同，先列時刻，再找重合。

A車從6:00起每15分鐘發車，B車從6:05起每20分鐘發車。以6:00為0，A的時刻為0、15、30、45……；B為5、25、45……，首次同時是6:45。找到第一次後，再隔lcm(15,20)=60分鐘重合，所以下一次為7:45。不能把首次重合直接算成6:00加60分鐘。

11 · 學完馬上練

兩數乘積關係：每個質數的次方各分配一次。

對任意正整數a、b，把每種質數的次方列出；沒有的視為0次。最大公因數取較小次方，最小公倍數取較大次方。兩者相乘時，指數相加，就是原來兩個次方的和。

例如24×36 = 12×72 = 864。這個公式可驗算，也可在已知三個數值時反求第四個。

三數不可直接照搬。例如2、4、8的最大公因數2，最小公倍數8，兩者相乘16，不等於2×4×8=64。最小與最大次方不能補回中間那個次方。

12 · 學完馬上練

換個情境，還能自己列出整除條件嗎？

「最多」「最少」只是題目的要求，不是選公式的密碼。先決定未知數代表什麼，再問它必須整除哪些量，或必須被哪些量整除。

鋪地磚：邊長必須把長和寬都分完。

長180公分、寬126公分的長方形，用同樣大的正方形地磚鋪滿，不裁切、不留縫。磚邊長s須同時整除180與126，所以最大邊長為gcd(180,126)=18公分；總片數為(180÷18)×(126÷18)=70。18是邊長，不是片數。

從總量反求原數：公式之外還要檢查互質。

兩個正整數的最大公因數是6、最小公倍數是180，可寫成a=6x、b=6y，且x、y必互質。因為lcm(a,b)=6xy，得到xy=30。互質因數配對有(1,30)、(2,15)、(3,10)、(5,6)，對應(6,180)、(12,90)、(18,60)、(30,36)。如果只要求乘積正確，卻不檢查x、y互質，可能選到最大公因數不對的數。

題型對照：本單元習作練習卷的標準分解式、三數GCD／LCM、分堆題。此處用不同數值檢查能否遷移，不以背下例題作為通過標準。

沿著三角形種樹，頂點不種要怎麼算？

三角形三邊長分別是105、135、150公尺。先從三個頂點起，沿各邊以同樣間距標出位置，再略過頂點不種樹。想要每段一樣長，而且最長。段長必須整除三邊，所以最大段長是15公尺。

三邊共有105÷15＋135÷15＋150÷15＝7＋9＋10＝26段。這是一圈，第一個位置和最後一個位置是同一處，所以原本有26個種樹位置。三個角改放風扇，不種樹。最後是26－3＝23棵。

要注意：封閉的一圈是「段數＝位置數」。直線的兩端都種樹才是「段數＋1」。

圍成一圈，棵數和直線兩端不同。

長140公尺、寬80公尺的長方形，四個頂點都種樹，沿邊等距。最大間距必須整除140與80，所以是20公尺。一圈周長440公尺，分為22段；因首尾接回同一棵，總共22棵，不再加1。直線兩端都種時才是段數+1；若頂點不種，還要明確規定頂點仍是同一間距格點，再扣除4棵。