惟一因子分解定理

質因數分解，或稱整數分解，是指將一個給定的正整數給表成數個正質數的乘積的行為。這一定理最早由歐幾里得在公元前三世紀發現，是初等數論的基礎。

根據算術基本定理，在不計書寫次序之狀況下，任意大於$1$的正整數皆唯一地寫成有限多個正質數的乘積，此又稱為該正整數的標準分解式，一般都會以其質因數的冪次來表達任意數的標準分解式。在整係數多項式中，多項式亦有類似的質因數分解的東西存在。

標準分解式

對於一個任意的大於$1$的整數$n$，我們做如下分解：

$$n = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_r^{\alpha_r}.$$

其中$p_1, p_2, \cdots, p_r$是素數，且$\alpha_1, \alpha_2, \cdots, \alpha_r \geqslant 1$，我們稱這種分解爲$n$的標準分解式。不過有時候，我們也只要求$\alpha_1, \alpha_2, \cdots, \alpha_r \geqslant 0$。

例如：$45$的標準分解式就是$3^2 \times 5$、$676$的標準分解式就是$2^2 \times 13^2$、$8128$的標準分解式就是$2^6 \times 127$。

性質

運用這一定理可以對公因數和公倍數做一個具體的刻畫： 設有如下$a, b$的分解式（非標準的，其中$p_i$是所有$a, b$的因數）：

$$a = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_r^{\alpha_r} \quad b = p_1^{\beta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_r^{\beta_r}.$$

則

1. $a \mid b$當且僅當$\alpha_i \leqslant \beta_i, 1 \leqslant i \leqslant r;$
2. $(a, b) = p_1^{\gamma_1} p_2^{\gamma_2} p_3^{\gamma_3} \cdots p_r^{\gamma_r}, \gamma_i = \min \{ \alpha_i, \beta_i \}, 1 \leqslant i \leqslant r;$
3. $[a, b] = p_1^{\delta_1} p_2^{\delta_2} p_3^{\delta_3} \cdots p_r^{\delta_r}, \delta_i = \max \{ \alpha_i, \beta_i \}, 1 \leqslant i \leqslant r.$

據此可證明有關的結論。

應用

質因數分解在密碼學等領域有相關的應用。雖然質因數分解的概念容易理解，但要知道一個很大的數的質因數分解形式非常地困難，甚至於電腦也很難在短時間內就找到某數的質因數分解形式。

參見

• 公因數
• 質數
• 輾轉相除法

上下節

• 上一節：公倍數
• 下一節：同餘