公因數

公因數

公因數（Common Divisor）是指能同時整除兩個或兩個以上整數的因數。例如，數字8和12的公因數有1、2、4，因為這些數字都能同時整除8和12。

• 因數：若整數a能被整數b整除（沒有餘數），則稱b是a的因數

• 公因數：兩個或多個整數共有的因數

• 最大公因數（GCD）：一組整數的所有公因數中最大的那個

1. 普遍性：任何兩個整數至少有一個公因數1

2. 有限性：兩個不全為零的整數的公因數個數是有限的

3. 倍數關係：若a是b的倍數，則b的所有因數都是a和b的公因數

4. 交換律：a和b的公因數與b和a的公因數完全相同

列舉法

1. 分別列出各數的所有因數

2. 找出共同的因數

範例：求12和18的公因數

• 12的因數：1, 2, 3, 4, 6, 12

• 18的因數：1, 2, 3, 6, 9, 18

• 公因數：1, 2, 3, 6

質因數分解法

1. 將各數分解為質因數的乘積

2. 取各數共有的質因數（次數取較小的）相乘

範例：求36和60的公因數

• 36 = 2² × 3²

• 60 = 2² × 3 × 5

• 公有質因數：2² × 3 = 12

輾轉相除法（歐幾里得算法）

適用於較大數字的計算：

1. 用較大數除以較小數，得餘數

2. 用除數除以餘數，得新餘數

3. 重複直到餘數為0，最後的非零餘數就是最大公因數

最大公因數（Greatest Common Divisor，簡稱GCD）是一組數中最大的公因數。求最大公因數的方法包括：

1. 列舉所有公因數後取最大值

2. 質因數分解法

3. 輾轉相除法

性質：

• GCD(a,b) = GCD(b,a)

• GCD(a,b) = GCD(-a,b)

• GCD(a,0) = |a|

• 若GCD(a,b)=d，則存在整數x,y使ax+by=d

1. 分數約簡：用分子分母的最大公因數約分

2. 數論問題：解決同餘方程等問題

3. 工程計算：計算最小公倍數的基礎

4. 編程算法：加密算法等領域的重要基礎

1. 最小公倍數（LCM）：與最大公因數有關係 LCM(a,b) × GCD(a,b) = a×b

2. 互質：當兩個數的最大公因數為1時，稱這兩個數互質

3. 擴展歐幾里得算法：不僅計算GCD，還能找到滿足貝祖等式的係數

1. 0與任何數：GCD(0,a) = |a|

2. 相同數字：GCD(a,a) = |a|

3. 連續整數：任何兩個連續整數的公因數只有1

4. 質數之間：不同質數的公因數只有1

公因數的概念最早出現在古希臘數學家歐幾里得的《幾何原本》中，其中記載了求最大公因數的輾轉相除法。中國古代的《九章算術》也有類似的方法記載。