互素

1. 概述

于 初等数论 中, 互素 描述两个 整数 没有除 外的共同 因数. 它等价于二者的 最大公因数 为 , 并可通过 裴蜀恒等式 转化为整数线性组合.

2. 定义

定义 1 (互素)

设 . 称 与 互素, 当：

3. 例子

例子 2 (初步例子)

• 与 互素, 因为 ;
• 与 不互素, 因为 .

4. 相关性质

命题 3 (互素的裴蜀判据)

设 . 则 与 互素 当且仅当存在 使：

证明 4 (互素的裴蜀判据)

充分性 ( )

若 , 则由 裴蜀恒等式, 存在 使 .

必要性 ( )

若 , 则 的任意公因数都整除 , 故 .

命题 5 (互素性对乘积的保持)

设 . 若 与 互素, 且 与 互素, 则 与 互素.

证明 6 (互素性对乘积的保持)

由 互素的裴蜀判据, 存在 使 且 . 两式相乘得：

再由 互素的裴蜀判据, 与 互素.

命题 7 (同余式中的互素消去律)

设 且 . 若 且 , 则 .

证明 8 (同余式中的互素消去律)

由 得 . 又 , 故由 Euclid 引理的一般形式, , 即 .

5. 相关概念

• 最大公因数
• 两两互素
• 素数
• 模逆元
• 同余

6. 术语翻译

中文	英文
互素	coprime / relatively prime
两两互素	pairwise coprime

初等数论