GRE 指南/最大公因數
兩個數的最大公因數是它們共同擁有的素因子的乘積，且每個素因子出現的次數相同。
例如，60 和 48 的最大公因數是 12。
60 48
/ \ / \
2 30 2 24
/ \ / \
2 15 2 12
/ \ / \
3 5 2 6
/ \
2 3
60 等於 2(2)(3)(5)，而 48 等於 2(2)(2)(2)(3)。它們共同擁有的素因子是 2，2 和 3，它們的乘積為 12。
1. 180 和 216 的最大公因數是多少？
2. 如果 84 和 y 的最大公因數是 6，而 125 和 y 的最大公因數是 5，那麼 y 的最小可能值是多少？
3. 120 和 192 的最大公因數，與 128 和 192 的最大公因數，哪個更大？
1. 36
180 216
/ \ / \
2 90 2 108
/ \ / \
2 45 2 54
/ \ / \
3 15 3 18
/ \ / \
3 5 3 6 / \ 2 3
180 的素因子分解是 2(2)(3)(3)(5)，而 216 的素因子分解是 2(2)(2)(3)(3)(3)。它們的共同素因子是 2(2)(3)(3)，即 36。
2. 30
如果 84 和 y 的最大公因數是 6，那麼 y 至少必須包含素因子 2 和 3。如果 125 和 y 的最大公因數是 5，那麼 y 必須包含 5 作為因子。因此，y 至少等於 2(3)(5)，即 30。
3. 128 和 192 的最大公因數
這個問題需要確定每個數的素因子分解。
120 192 128
/ \ / \ / \
2 60 2 96 2 64
/ \ / \ / \
2 30 2 48 2 32
/ \ / \ / \ 2 15 2 24 8 4 / \ / \ / \ / \ 3 5 2 12 4 2 2 2 / \ / \ 2 6 2 2 / \ 2 3
192 的素因子分解是 2(2)(2)(2)(2)(2)(3)。因此，它與 120 的最大公因數是 2(2)(2)(3)，即 24，而它與 128 的最大公因數是 2(2)(2)(2)(2)(2)，即 64。