互质
| 互质 | |
|---|---|
| 术语名称 | 互质 |
| 英语名称 | coprime |
| 别名 | 互素, 既约, mutually prime, relatively prime |
1 和 -1 是任意两个整数的公因数，若对任意两个数，其最大公因数为 1 或者说两个数只有这两个公因数，则称两个数互质/互素(coprime)。
定义
| 互质 | |
|---|---|
| 关系名称 | 互质 |
| 关系符号 | [math]\displaystyle{ \operatorname{gcd}()=1 }[/math],[math]\displaystyle{ \perp }[/math] |
| Latex | \operatorname{gcd}()=1, \perp
|
| 关系对象 | 整数 |
| 关系元数 | 2 |
| 全集 | [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z} }[/math] |
对整数 [math]\displaystyle{ a, b }[/math] ，若 [math]\displaystyle{ \operatorname{gcd}(a, b) = 1 }[/math] ，称整数 [math]\displaystyle{ a }[/math] 和整数 [math]\displaystyle{ b }[/math] 互质/互素 ([math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are coprime/relatively prime / [math]\displaystyle{ a }[/math] is coprime to [math]\displaystyle{ b }[/math] / [math]\displaystyle{ a }[/math] is (relatively) prime to [math]\displaystyle{ b }[/math])。
一般地，对整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] ，若 [math]\displaystyle{ \operatorname{gcd}(a_1, a_2, \dots, a_n) = 1 }[/math] ，也称整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 互质/互素(coprime)；若 [math]\displaystyle{ (\forall i, j)(i\neq j \rightarrow \operatorname{gcd}(a_i, a_j) = 1) }[/math] ，则称整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 两两互质/两两互素(pairwise coprime / pairwise relatively prime)。
性质
对任意整数，以下和互质等价：
- 没有非 1、-1 的数能同时整除这些数。
- [math]\displaystyle{ (\exists x_1, x_2, \dots, x_n \in \mathbb{Z}) (x_1 a_1 + x_2 a_2 + \dots + x_n a_n = 1) }[/math] 。
对任意整数，以下和两数互质等价：
- 两数互质，则每个数在另一个数的模 n 剩余类环中是一个可逆元；如果两个数本身是质数，则是一个生成元。
- 对任意两个正整数，两数的最小公倍数是两数之积。（对负整数可以加绝对值成立，但对至少一方为 0 的情况无法成立）
根据定义：
- 1 与任意整数互质。
- 质数与任意不是其倍数的整数互质。
结合 Bézout 定理很容易推出：
- [math]\displaystyle{ a \mid bc \land \operatorname{gcd}(a, b) = 1 \rightarrow a \mid c }[/math]
- 对质数 [math]\displaystyle{ p }[/math] ，有 [math]\displaystyle{ p\mid ab \rightarrow p\mid a \lor p\mid b }[/math]