模逆元

1. 概述

于 初等数论 中, 模逆元 是乘法逆元在同余意义下的对应物. 一个整数模 可逆的充要条件是它与 互素, 其逆元可由 扩展 Euclid 算法 求得.

2. 定义

定义 1 (模逆元)

设 且 , . 若

则称 为 关于模 的 乘法逆元, 简称 模逆元.

记号 2 (模逆元)

关于模 的 模逆元 记作 .

3. 例子

例子 3 ( 模 的逆元)

因为 , 所以 是 关于模 的 模逆元. 整数 都代表同一个逆元, 因为它们属于同一个模 剩余类.

4. 相关性质

定理 4 (模逆元的存在判据)

设 且 , . 则 关于模 存在 模逆元, 当且仅当

证明 5 (模逆元的存在判据)

充分性 ( )

若 , 则存在 使 . 由 互素的裴蜀判据, .

必要性 ( )

若 , 则由 互素的裴蜀判据, 存在 使 . 因而 , 即 是 的 模逆元.

命题 6 (模逆元的唯一性)

设 且 , . 若 关于模 存在 模逆元, 则该模逆元在模 意义下具有 唯一性.

证明 7 (模逆元的唯一性)

若 都是 关于模 的 模逆元, 则：

由 模逆元的存在判据 有 , 再由 同余式中的互素消去律 得 .

推论 8 (用扩展 Euclid 算法求模逆元)

设 且 , , . 若 扩展 Euclid 算法 给出

则 是 关于模 的 模逆元.

证明 9 (用扩展 Euclid 算法求模逆元)

将等式模 化简即得 , 故由 模逆元 的定义即得结论.

5. 相关概念

• 互素
• 扩展 Euclid 算法
• 线性同余方程
• 整数模 环

6. 术语翻译

中文	英文
模逆元	modular multiplicative inverse

初等数论