查看“︁互质”︁的源代码

[[分类:整除理论]]
{{InfoBox
|name=互质
|eng_name=coprime
|aliases=互素,既约,mutually prime,relatively prime
}}
1 和 -1 是任意两个整数的公因数，若这是两数最大公因数，则只有这两个公因数，此时称两个数'''互质'''/'''互素'''('''coprime''')。

== 定义 ==

{{Relation
|name=互质
|symbol=<math>\operatorname{gcd}()=1</math>,<math>\perp</math>
|latex=\operatorname{gcd}()=1,\perp
|operand_relation=整数
|cartesian=<math>\mathbb{Z}\times\mathbb{Z}</math>
}}
对整数 <math>a, b</math> ，若 <math>\operatorname{gcd}(a, b) = 1</math> ，称整数 <math>a</math> 和整数 <math>b</math> '''互质'''/'''互素''' (<math>a</math> and <math>b</math> are '''coprime'''/'''relatively prime''' / <math>a</math> '''is (relatively) prime to''' <math>b</math>)。

一般地，对整数 <math>a_1, a_2, \dots, a_n</math> ，若 <math>\operatorname{gcd}(a_1, a_2, \dots, a_n) = 1</math> ，也称整数 <math>a_1, a_2, \dots, a_n</math> '''互质'''/'''互素'''('''coprime''')；若 <math>(\forall i, j)(i\neq j \rightarrow \operatorname{gcd}(a_i, a_j) = 1)</math> ，则称整数 <math>a_1, a_2, \dots, a_n</math> '''两两互质'''/'''两两互素'''('''pairwise coprime''' / '''pairwise relatively prime''')。

== 性质 ==

以下和互质等价：
* 没有非 1、-1 的数能同时整除这些数。
* <math>(\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 剩余类环]]中是一个[[生成元]]。
* 两数的[[最小公倍数]]是两数之积。

根据定义：
* 质数与任意整数互质。

结合<ins>裴蜀</ins>定理很容易推出：
* <math>a \mid bc \land \operatorname{gcd}(a, b) = 1 \rightarrow a \mid c</math>
** 对质数 <math>p</math> ，有 <math>p\mid ab \rightarrow p\mid a \lor p\mid b</math>


{{整除与质数}}