互质
| 互质 | |
|---|---|
| 术语名称 | 互质 |
| 英语名称 | coprime |
| 别名 | 互素, 既约, mutually prime, relatively prime |
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 (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] 。
以下和两数互质等价：
根据定义：
- 质数与任意整数互质。
结合裴蜀定理很容易推出：
- [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]
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |