夏令營有 54 名男生和 48 名女生。要把他們分組，使每組的男生人數相同、女生人數也相同，而且每個人都在某一組裡。最多能分成幾組？

Step-by-step solution

1. 1

   把條件翻譯成整除關係。 如果分成 $g$ 組，每組有 $b$ 名男生、$h$ 名女生，那麼 $gb=54$、$gh=48$。所以 $g$ 必須同時整除 $54$ 與 $48$——組數是一個公因數，而「組數盡可能多」要的就是最大公因數。

2. 2

   把兩個總人數各自分解質因數。

   $54=2\times 3^3,\qquad 48=2^4\times 3$

3. 3

   對每個共同的質因數取較小的指數。 兩者共有的質因數是 $2$ 與 $3$：

   $\gcd(54,48)=2^{\min(1,4)}\times 3^{\min(3,1)}=2\times 3=6$

4. 4

   確認這樣分組真的可行。 當 $g=6$ 時，

   $\frac{54}{6}=9\ \text{（每組男生數）},\qquad \frac{48}{6}=8\ \text{（每組女生數）}$

   兩個都是整數，而且 $6\times 9=54$、$6\times 8=48$，沒有人被剩下。

5. 5

   驗證 $7$ 組或更多為什麼不可能。 $54$ 的因數是 $1,2,3,6,9,18,27,54$，$48$ 的因數是 $1,2,3,4,6,8,12,16,24,48$。它們的公因數只有 $1,2,3,6$，所以 $6$ 確實是最大的——任何比它大的數，至少除不盡這兩個總數中的一個。再交叉驗證一次，輾轉相除法給出 $54=48+6$、$48=8\times 6+0$，所以 $\gcd=6$。