最大公因數的算法與切割

MoAI - 您的AI助手

建立於 2026年11月10日

學習重點 掌握因數、倍數、公因數、最大公因數的關係，能由因數條件反推短除法中剩餘的商的限制，並求其最小值。 熟悉列舉因數法、質因數分解法與短除法。三種算法的本質相同，都是找出兩數共有的因數。 判斷一種做法是否正確，要看兩件事：每一步是否真的同時整除兩數，以及最後剩下的兩數是否互質。不能因為寫法和課本不同就判錯。 處理矩形切成相同正方形的問題時，長、寬都必須能被正方形邊長整除，切出的總數也要符合。只比面積不夠。 最大公因數的概念依「具體列舉 → 辨認質因數結構 → 程序化短除」的順序發展。 核心觀念 一、因數與最大公因數的基本意義 若 A＝a×k，其中 a、k 為正整數，就稱 a 是 A 的因數，A 是 a 的倍數。兩數共同具有的因數稱為公因數，其中最大者就是最大公因數。 以 24 與 16 為例： 24 的因數有 1、2、3、4、6、8、12、24。 16 的因數有 1、2、4、8、16。 公因數為 1、2、4、8，所以最大公因數是 8。 兩數的每一個公因數，也都是最大公因數的因數。 互質是指兩數的最大公因數為 1，不表示兩數本身都是質數。例如 8 與 9 都是合數，但兩數互質。 二、質因數分解：共同質因數取較少的個數 質因數分解是把正整數寫成質數相乘的形式。求最大公因數時，只保留兩數共有的質因數；每種質因數取兩數中較少的個數，也就是較小的指數。 例如 60＝2×2×3×5，90＝2×3×3×5。兩數共有一個 2、一個 3、一個 5，所以最大公因數是 2×3×5＝30。60 多出的一個 2 與 90 多出的一個 3，都不能算進去。 提取公因數時，不一定要先分解到全部是質數。例如 60＝10×6、90＝10×9，先提出共同因數 10，再求 6 與 9 的最大公因數 3，同樣得到 10×3＝30。只要共同部分提取完整，不同的拆法都正確。 三、短除法的原理與停止條件 短除法的依據是：若 A＝d×a、B＝d×b，則 A、B 的最大公因數等於 d 乘以 a、b 的最大公因數。所以可以一層一層提出共同因數。步驟如下： 找出能同時整除目前兩數的公因數，通常選共同的質因數。 將兩數同時除以這個公因數，寫下兩個商。 重複上述步驟，直到最後兩個商互質。 把左側所有共同除數相乘，就是原來兩數的最大公因數。 例如 60 與 90 可依序同除以 2、3、5，最後剩 2 與 3，最大公因數為 2×3×5＝30。也可以先同除以 6 得 10 與 15，再同除以 5 得 2 與 3，結果一樣是 30。共同除數用合數也可以，只要確實同時整除，且最後剩下的兩數互質。 若停在 6 與 9 就結束，兩數仍有公因數 3，表示尚未完成。反過來說，最後的商不必有一個是 1，只要互質就可以停止。 四、由已知因數反推短除法中的未知數 短除法出現未知數時，先把除法關係改寫成乘法。設左側共同除數的乘積為 D，最後兩個商為 m、n，則： A＝D×m，B＝D×n，且 m、n 必須互質（短除法已完成）。 已知 a 是 A 的因數，表示 a 能整除 D×m。先約去 a 與 D 共有的部分，剩下的部分必須由 m 提供。也就是說，m 必須是「a ÷（a 與 D 的最大公因數）」的倍數。B 的條件用同樣方法處理。 例如共同除數只有 2（D＝2），且 44 是 A 的因數、26 是 B 的因數： 44 與 2 的最大公因數是 2，44÷2＝22，所以 m 是 22 的倍數，最小為 22。 26 與 2 的最大公因數是 2，26÷2＝13，所以 n 是 13 的倍數，最小為 13。 22 與 13 互質，符合短除法的停止條件，所以 m＋n 的最小值為 22＋13＝35。 解題順序是：先各自求出最小可能值，再檢查互質等所有條件。若兩個最小值不互質，就必須往上調整。不能直接把題目給的兩個因數相加。 五、矩形切成相同正方形：邊長與個數同時成立 設矩形長 L、寬 W，正方形邊長 s。要剛好切滿，L÷s 與 W÷s 都必須是正整數。正方形總數為： 切割總數＝（L÷s）×（W÷s）＝L×W÷s² 若指定切成 N 個相同正方形，可先由 s²＝L×W÷N 求出候選邊長，再檢查長、寬是否都是 s 的整數倍。面積符合只是第一關，兩個方向都要排得整齊。 更快的判斷方法是看長寬比。把長：寬化成最簡整數比 p：q，則能切出的正方形個數只能是 p×q×k²（k 為正整數）。以 12 個為例，可能的排法如下： 最簡長寬比排法（長方向×寬方向）個數 3：16×2（k＝2）12 4：34×3（k＝1）12 12：112×1（k＝1）12 例如： 12 公尺×4 公尺的矩形，比為 3：1，切成邊長 2 公尺的正方形，排成 6×2＝12 個。 8 公尺×6 公尺的矩形，比為 4：3，切成邊長 2 公尺的正方形，排成 4×3＝12 個。 可見長寬不同的矩形，也可能切出同樣個數的正方形。 若長、寬是分數，先通分或換成較小的共同單位，化為整數比後再用同樣方法判斷。題目沒有限定邊長為整數時，正方形邊長可以是分數，不能因為長寬是分數就判定不能切。 當長、寬都是整數且要求正方形邊長為整數時，邊長必須是長、寬的公因數。邊長取最大公因數時，正方形最大、個數最少。 六、最大公因數算法的概念發展順序 方法做法概念位置 列舉因數法分別列出兩數的因數，找出共同且最大者。最具體，直接建立「公因數」與「最大」的意義。 質因數分解法把兩數寫成質數連乘，取共同質因數相乘。由乘法結構看出公因數的組成。 短除法同時除以共同因數，左側相乘。最抽象，把前面的概念整理成有效率的程序。 合理的教學順序是列舉因數法 → 質因數分解法 → 短除法。題目若以甲、乙、丙代表不同做法，先辨認每一種做法實際屬於哪一種方法，再依此順序排列。 常考陷阱 把「公因數」當成「最大公因數」：找到一個能同時整除的數還不夠，要確認共同因數已全部提出。 把短除法最後兩個商也乘進去：求最大公因數只乘左側的共同除數。左側再乘上最後兩個商，求的是最小公倍數。 認為共同除數只能是質數：用合數（如 6、10）提取也正確，判斷重點是能否同時整除，以及最後兩數是否互質。兩種不同寫法可能都對。 看到剩下兩數是合數，就認為還沒做完：停止的標準是互質，不是兩數都為質數。 求 m＋n 最小值時，直接把已知因數相加：必須先約去和共同除數重複的部分，再檢查 m、n 是否互質。直接相加的數值通常是錯誤選項。 指定切割個數卻直接用最大公因數當邊長：最大公因數對應的是最少個數。指定個數要用面積與長寬比另行判斷。 只看面積能否平均分配：還要確認長、寬各能排下整數個正方形。 看到分數長寬就判定不能切：化成整數比後，只要比例符合 p×q×k²＝指定個數，就能剛好切割。 記憶口訣 共同因數逐步提，剩下互質才停筆；左側相乘是最大，兩個餘商別乘入。 反推未知先約去，各取最小再驗互質。 切正方，看長寬比，p 乘 q 乘 k 平方；列舉懂意義，分解看結構，短除省步驟。