公因數和最大公因數

在數學中，特別是在整數論中，公因數和最大公因數是兩個相關的概念，它們用來描述兩個或多個整數之間的關係。

1. 公因數（Common Factor）： 兩個或更多個整數的公因數是這些整數都能被整除的數。例如，24和36的公因數包括1, 2, 3, 4, 6, 12和24。這些數都是24和36都能被整除的。

2. 最大公因數（Greatest Common Divisor，GCD）： 最大公因數是兩個或更多個整數共有的最大因數。對於給定的整數集合，最大公因數通常用符號gcd(a, b, ...)來表示。例如，gcd(24, 36) = 12，因為12是24和36的最大公因數。

最大公因數可以用質因數分解來找出。例如，要找出gcd(24, 36)，我們可以先將24和36分解為質因數：

24 = 2^3 3^1 36 = 2^2 3^2

然後，我們從兩個數的質因數分解中找出共同的因數，並將它們相乘：

gcd(24, 36) = 2^2 * 3^1 = 12

最大公因數有幾個重要的性質：

• 對於任何整數a和b，gcd(a, b)是唯一的，也就是說，對於特定的a和b，最大公因數只有一個。
• gcd(a, b) = gcd(b, a)，這意味著最大公因數對調順序不敏感。
• 如果a和b互質（沒有除了1以外的公因數），那麼gcd(a, b) = 1。
• 對於任何整數a和b，有gcd(a, b) ≤ max(a, b)。

在實際應用中，最大公因數有許多用途，例如在數論、代數、幾何和工程學中。最大公因數的計算可以使用質因數分解、埃拉托斯特尼篩法、更相剋除法或輾轉相除法（也稱為歐幾里得算法）等方法來完成。