最大公因子

最大公因子, 又叫最大公约数, 是几个整数最大的公共因子, 或更一般地, 交换环中几个元素在整除偏序下最大的公共因子.

最大公因数是初等数论的主要研究对象, 具有丰富的性质.

1定义

定义 1.1. 整数 $a_1,a_2,\cdots ,a_n$ 的最大公因数 $\gcd (a_1,a_2,\cdots ,a_n)$ 是指满足$$d\mid a_i(i=1,2,\cdots ,n)$$的最大整数 $d$.

最大公因数也常记为 $(a_1,a_2,\cdots ,a_n)$.

容易知道任何整数的最大公因数总是存在的.

2性质

•	最大公因数与整数的次序无关.
•	若 $a\mid b$, 则 $(a,b)=a$.
•	$((a_1,\cdots ,a_k),(a_{k+1},\cdots ,a_n))=(a_1,\cdots ,a_n)$.
•	几个整数的公因数总是整除最大公因数, 即若存在一个数 $d$ 使$$d\mid a_i(a_i\in \mathbb{Z},i=1,2,\cdots n),$$则 $d\mid (a_1,a_2,\cdots ,a_n)$.
•	对任意 $m\in \mathbb{Z}$, $$(m{a}_1,m{a}_2,\cdots ,m{a}_n)=m(a_1,a_2,\cdots a_n).$$
•	对任意 $m\in \mathbb{Z}$, 若$$m\mid a_i(a_i\in \mathbb{Z},i=1,2,\cdots ,n),$$则$$\left(\frac{a_1}{m},\frac{a_2}{m},\cdots ,\frac{a_n}{m}\right)=\frac{(a_1,a_2,\cdots a_n)}{m}.$$
•	若 $a,c$ 互素, 即 $(a,c)=1$, 则对任意整数 $c$, $(ab,c)=(b,c)$.
•	若 $a,b$ 互素, 则对任意整数 $d$, $(ab,d)=(a,d)(b,d)$.
•	对任意 $x,y\in \mathbb{Z}$, 总有 $(a,b)\mid (ax+by)$. 一般地, $(a_1,a_2,\cdots ,a_n)$ 是集合$$\{a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n\mid x_i\in \mathbb{Z},i=1,2,\cdots ,n\}$$中的最小正整数. 这个性质又称 Bézout 定理.
•	$(a,b)[a,b]=\mid ab\mid$, 其中 $[a,b]$ 是两整数的最小公倍数.
•	对任意 $a,b,q\in \mathbb{Z}$, 均有 $(a,qa+b)=(a,b)$. 这是辗转相除法的原理.

此外最大公因数可用整数的分解式写出.

定理 2.1. 如果整数 $a_i(i=1,2,\cdots ,n)$ 被分解成$$a_i=p_1^{s_{i1}}{p}_2^{s_{i2}}{p}_3^{s_{i3}}\cdots ,s_{ij}\ge 0,p_j<p_{j+1},j=1,2,\cdots ,$$其中 $p_1,p_2,\cdots$ 都是素数, 则$$(a_1,a_2,\cdots ,a_n)=p_1^{b_1}{p}_2^{b_2}{p}_3^{b_3}\cdots ,$$其中$$b_j=\min \{s_{1j},s_{2j},\cdots ,s_{nj}\},j=1,2,\cdots .$$

证明. 由算术基本定理, 我们可以设$$(a_1,a_2,\cdots ,a_n)=p_1^{b_1}{p}_2^{b_2}{p}_3^{b_3}\cdots ,b_j\ge 0,p_j<p_{j+1},j=1,2,\cdots .$$

由 $(a_1,a_2,\cdots ,a_n)\mid a_i,i=1,2,\cdots ,n$ 知$$b_j\le s_{ij}.$$

又最大公因数是最大的公因数, 所以$$b_j=\min \{s_{1j},s_{2j},\cdots ,s_{nj}\},j=1,2,\cdots .$$

$\square$

上面的绝大多数性质都可以用此定理证明.

3计算

通常, 我们使用辗转相除法来计算两个整数的最大公因数.

4推广

(推广到主理想整环、唯一分解整环、Prüfer 环上.)

5相关概念

•	互素
•	最小公倍数
•	辗转相除法

术语翻译

最大公因子 • 英文 greatest common divisor • 德文 größte gemeinsame Teiler • 法文 plus grand commun diviseur • 拉丁文 maximus communis divisor