公因數

一個數$a$稱為兩數$m$與$n$的公因數，是説$a$能整除$m$，且$a$能整除$n$。$m$和$n$的所有公因數中，如果$m$和$n$不全爲$0$，則必有一個最大的（且是正數）的公因數，稱為$m$與$n$最大公因數，一般記作$d = \gcd(m,n)$或$d = (m,n)$。

除了直接分別列舉兩數的因數，或將兩個整數作質因數分解，再將質因數分解中共同的項目找出來，以求其最大公因數外，亦可用輾轉相除法來找其最大公因數。

特別地，儅不全爲零的$a, b$滿足$(a, b) = 1$時，$a$和$b$只有公因子$\pm 1$，這時稱$a$與$b$互素（或互質）。

推廣

兩個數定義出來的公因數以及最大公因數概念不難推廣到$n$個數中去：

任意一組整數$\{ a_i \}_{i=1}^n$必有公因數（例如$\pm 1$），當著組數不全為$0$時，它們的公因數只有有限多個。我們將它們這些公因數中最大的一個公因數稱爲這組數的最大公因數。

可以證明，在求解最大公因子時可以先求任意兩個數的最大公因子，將其結果再與其它求最大公因子，逐個將所有數都涵蓋進去。

基本性質

這裏以兩個不全爲零的數爲例。

1. $(a, b) = (b, a);$
2. $(a, b) = (|a|, b) = (-a, b)$
3. $(a, b) = (a, b+ka), \forall k \in \Z;$
4. $m(a, b) = (ma, mb), \forall m \in \Z;$
5. 若$(a, b) = d$，則$\left( \dfrac{a}{d}, \dfrac{b}{d} \right) = 1;$
6. $a, b$的所有公因子都是最大公因子的因子。

貝祖等式

若$d$是$m$與$n$的最大公因數，則存在有兩整數$x$和$y$(不一定是正整數)，使得$mx+ny = d$，此等式稱為貝祖等式。不難將它推廣到$n$個數的情形。

環中的公因子

設$R$是整環，$a,b\in R$，如果存在$d$使得$d \mid a, d \mid b$，我們就稱$d$是$a, b$的公因子，用理想的語言來説就是$(a, b) \subseteq (d)$，這裏記號$(a,b)$代表$a, b$兩個元素生成的理想。

下面我們定義“最大”公因子的概念，假設同上，在所有的公因子中，集合包含意義下的最小理想$(d_m)$對應的生成元$d_m$稱爲是$a, b$的最大公因子，即$\forall d \in \{ d \in R: (a, b) \subseteq (d) \}, (d_m) \subseteq (d).$用通俗的語言來説就是：$d_m \mid a, d_m \mid b$且由$d \mid a, d \mid b$可推出$d_m \mid d.$

需要注意的是，這樣定義的最大公因子常記作$\gcd (a, b)$，它不是唯一的，$(d_m)$中的任意一個非零非單位元素都可以是最大公因子，因此這個幾號應該理解爲一個集合，這些最大公因子之間是相伴的。

在特例整數環上，最大公因子相差一個符號，是因爲相伴關係中的單位只有$\pm 1.$

上下節

• 上一節：素數
• 下一節：輾轉相除法