模m的乘法逆元
定义
对
于
整
数
a
，
m
，
如
果
存
在
整
数
b
，
满
足
a
b
=
1
(
m
o
d
m
)
，
则
称
b
是
a
的
模
m
乘
法
逆
元
。
其
充
分
必
要
条
件
是
a
和
m
互
素
，
即
a
和
m
的
最
大
公
因
数
为
1
。
用
式
子
表
示
为
：
g
c
d
(
a
,
m
)
=
1
对于整数 a，m，如果存在整数b，满足 ab=1(mod \,\,m)，则称b是a的模m乘法逆元。\\ 其充分必要条件是 a和m互素，即 a和m的最大公因数为1。用式子表示为： gcd(a,m) = 1
对
于
整
数
a
，
m
，
如
果
存
在
整
数
b
，
满
足
a
b
=
1
(
m
o
d
m
)
，
则
称
b
是
a
的
模
m
乘
法
逆
元
。
其
充
分
必
要
条
件
是
a
和
m
互
素
，
即
a
和
m
的
最
大
公
因
数
为
1
。
用
式
子
表
示
为
：
g
c
d
(
a
,
m
)
=
1
迭代算法
在
下
面
的
表
格
中
，
在
第
i
步
，
即
第
i
行
，
成
立
：
a
∗
x
i
=
r
i
(
m
o
d
m
)
,
其
中
y
0
=
0
,
x
0
=
1
,
x
i
=
y
i
−
1
−
x
i
−
1
∗
q
i
,
y
i
=
x
i
−
1
,
q
i
=
k
i
(
∣
m
∣
>
∣
r
0
∣
>
∣
r
1
∣
>
∣
r
2
∣
>
∣
r
3
∣
>
.
.
.
>
∣
r
i
∣
>
.
.
.
)
在下面的表格中，在第i步，即第i行，成立：a*x_i = r_i (mod \,\, m)\,,\,其中 \\ y_0 = 0\,,\,x_0 = 1\,,\,x_i =y_{i-1}-x_{i-1}*q_i\,,\,y_i = x_{i-1},\,\,q_i = k_i \\ (|m| > |r_0| > |r_1| > |r_2| > |r_3| > … > |r_i| > …)
在
下
面
的
表
格
中
，
在
第
i
步
，
即
第
i
行
，
成
立
：
a
∗
x
i
=
r
i
(
m
o
d
m
)
,
其
中
y
0
=
0
,
x
0
=
1
,
x
i
=
y
i
−
1
−
x
i
−
1
∗
q
i
,
y
i
=
x
i
−
1
,
q
i
=
k
i
(
∣
m
∣
>
∣
r
0
∣
>
∣
r
1
∣
>
∣
r
2
∣
>
∣
r
3
∣
>
.
.
.
>
∣
r
i
∣
>
.
.
.
)
| i | 表达式 | y | x | q |
|---|---|---|---|---|
| 0 |
a = k 0 m + r 0 a=k_0m+r_0 a = k 0 m + r 0 |
0 | 1 |
k 0 k_0 k 0 |
| 1 |
m = k 1 r 0 + r 1 m=k_1r_0+r_1 m = k 1 r 0 + r 1 |
1 |
− k 1 -k_1 − k 1 |
k 1 k_1 k 1 |
| 2 |
r 0 = k 2 r 1 + r 2 r_0 = k_2r_1+r_2 r 0 = k 2 r 1 + r 2 |
− k 1 -k_1 − k 1 |
1 + k 1 k 2 1+k_1k_2 1 + k 1 k 2 |
k 2 k_2 k 2 |
| 3 |
r 1 = k 3 r 2 + r 3 r_1 = k_3r_2+r_3 r 1 = k 3 r 2 + r 3 |
1 + k 1 k 2 1+k_1k_2 1 + k 1 k 2 |
− k 1 − ( 1 + k 1 k 2 ) k 3 -k_1-(1+k_1k_2)k_3 − k 1 − ( 1 + k 1 k 2 ) k 3 |
k 3 k_3 k 3 |
| … | … | … | … | … |
|
i i i |
r i − 2 = k i ∗ r i − 1 + r i r_{i-2}=k_i*r_{i-1} +r_i r i − 2 = k i ∗ r i − 1 + r i |
x i − 1 x_{i-1} x i − 1 |
y i − 1 − x i − 1 ∗ q i y_{i-1}-x_{i-1}*q_i y i − 1 − x i − 1 ∗ q i |
k i k_i k i |
| … | … | … | … | … |
当
r
i
=
1
\,r_i=1\,
r
i
=
1
时，对应的
x
i
x_i
x
i
即为所求。
Note : 迭代算法要先考虑
初始条件
，再考虑迭代公式。
数学归纳法证明
可
以
验
证
，
a
x
0
=
r
0
+
k
0
m
,
a
x
1
=
r
1
+
k
1
m
构
造
r
0
=
k
2
r
1
+
r
2
,
x
2
=
x
0
−
x
1
k
2
使
得
：
a
x
2
=
r
2
+
k
2
m
当
i
≥
3
时
，
由
a
∗
x
i
−
2
=
r
i
−
2
+
k
i
−
2
∗
m
(
1
)
a
∗
x
i
−
1
=
r
i
−
1
+
k
i
−
1
∗
m
(
2
)
r
i
−
2
=
k
i
∗
r
i
−
1
+
r
i
(
3
)
得
：
a
(
x
i
−
2
−
x
i
−
1
∗
k
i
)
=
a
x
i
−
2
−
a
x
i
−
1
k
i
=
r
i
−
2
+
k
i
−
2
∗
m
−
(
r
i
−
1
+
k
i
−
1
∗
m
)
∗
k
i
=
(
r
i
−
2
−
r
i
−
1
k
i
)
+
(
k
i
−
2
−
k
i
−
1
k
i
)
m
=
r
i
+
(
k
i
−
2
−
k
i
−
1
k
i
)
m
得
：
x
i
=
x
i
−
2
−
x
i
−
1
∗
k
i
使
得
：
a
x
i
=
r
i
+
k
i
m
则
由
数
学
归
纳
法
知
，
上
述
构
造
方
法
成
立
。
可以验证，ax_0 = r_0+k_0m\,,\,ax_1 = r_1 + k_1m\,\,\\构造\,\,r_0 = k_2r_1 + r_2\,,\,x_2 = x_0 – x_1k_2\,\,\\使得：ax_2 = r_2+k_2m \\ 当i \ge 3 时，由\,\,\\\begin{aligned}a*x_{i-2} &= r_{i-2}+k_{i-2}*m \quad (1) \\ a*x_{i-1} &= r_{i-1}+k_{i-1}*m \quad (2) \\ r_{i-2} &= k_i*r_{i-1}+r_i \quad \quad (3) \\ 得：\\ a(x_{i-2}-x_{i-1}*k_i) &= ax_{i-2}-ax_{i-1}k_i \\ &= r_{i-2}+k_{i-2}*m – (r_{i-1}+k_{i-1}*m)*k_i \\ &= (r_{i-2}-r_{i-1}k_i)+(k_{i-2}-k_{i-1}k_i)m \\ &= r_i + (k_{i-2}-k_{i-1}k_i)m \\ 得：x_i &= x_{i-2}-x_{i-1}*k_i \\ 使得：& ax_i = r_i + k_im \\ 则由数学 & 归纳法知，上述构造方法成立。 \end{aligned}
可
以
验
证
，
a
x
0
=
r
0
+
k
0
m
,
a
x
1
=
r
1
+
k
1
m
构
造
r
0
=
k
2
r
1
+
r
2
,
x
2
=
x
0
−
x
1
k
2
使
得
：
a
x
2
=
r
2
+
k
2
m
当
i
≥
3
时
，
由
a
∗
x
i
−
2
a
∗
x
i
−
1
r
i
−
2
得
：
a
(
x
i
−
2
−
x
i
−
1
∗
k
i
)
得
：
x
i
使
得
：
则
由
数
学
=
r
i
−
2
+
k
i
−
2
∗
m
(
1
)
=
r
i
−
1
+
k
i
−
1
∗
m
(
2
)
=
k
i
∗
r
i
−
1
+
r
i
(
3
)
=
a
x
i
−
2
−
a
x
i
−
1
k
i
=
r
i
−
2
+
k
i
−
2
∗
m
−
(
r
i
−
1
+
k
i
−
1
∗
m
)
∗
k
i
=
(
r
i
−
2
−
r
i
−
1
k
i
)
+
(
k
i
−
2
−
k
i
−
1
k
i
)
m
=
r
i
+
(
k
i
−
2
−
k
i
−
1
k
i
)
m
=
x
i
−
2
−
x
i
−
1
∗
k
i
a
x
i
=
r
i
+
k
i
m
归
纳
法
知
，
上
述
构
造
方
法
成
立
。
C++代码实现
#include<iostream>
using namespace std;
long mod_reverse(long a,long m) // 若返回-1，则表示整数a关于模m的乘法逆元不存在
{
long y=0,x=1,r=a%m,q,temp,mInit=m;
if(r<0)r=r+m;
while((m%r)!=0) //已计算完第i步，如果还需要计算第i+1步
{
a=m;m=r;
q=a/m,r=a%m;
temp=x;x=y-x*q;y=temp;
}
if(r!=1)return -1;
if(x<0)x=x+mInit;
return x;
}
递归算法
主要基于
扩展欧几里得算法
扩展欧几里得算法
已知整数a、b，扩展欧几里得算法可以在求得a、b的
最大公约数
的同时，能找到整数x、y（其中一个很可能是负数），使它们满足下面的等式
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by = gcd(a,b)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
如果a是负数，可以把问题转化成
∣
a
∣
(
−
x
)
+
b
y
=
g
c
d
(
∣
a
∣
,
b
)
|a|(-x)+by = gcd(|a|,b)
∣
a
∣
(
−
x
)
+
b
y
=
g
c
d
(
∣
a
∣
,
b
)
然后令
x
′
=
−
x
x’=-x
x
′
=
−
x
当
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
g
c
d
(
a
,
b
)
=
1
则对应的
x
为
a
模
b
的
乘
法
逆
元
，
y
为
b
模
a
的
乘
法
逆
元
x为a模b的乘法逆元，y为b模a的乘法逆元
x
为
a
模
b
的
乘
法
逆
元
，
y
为
b
模
a
的
乘
法
逆
元
代码实现
写法一：
// C
unsigned int gcdExtended(int a, int b, int *x, int *y){
if (a == 0){
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
简单证明：
下面是错的
代
码
意
图
转
化
为
：
已
知
：
{
(
b
%
a
)
∗
x
1
=
1
(
m
o
d
a
)
(
1
)
a
∗
y
1
=
1
(
m
o
d
(
b
%
a
)
)
(
2
)
求
得
：
{
a
∗
x
=
1
(
m
o
d
b
)
(
3
)
b
∗
y
=
1
(
m
o
d
a
)
(
4
)
其
中
，
{
x
=
y
1
−
(
b
/
a
)
x
1
(
5
)
y
=
x
1
(
6
)
设
b
=
k
a
+
r
(
7
)
,
r
=
b
%
a
(
8
)
,
由
于
b
y
=
(
k
a
+
r
)
y
=
r
y
=
r
x
1
=
1
(
m
o
d
a
)
,
可
知
由
(
1
)
,
(
6
)
可
推
出
(
4
)
。
由
(
1
)
不
妨
设
r
x
1
=
1
+
d
a
(
9
)
,
由
(
2
)
不
妨
设
a
y
1
=
1
+
p
r
(
10
)
,
由
(
3
)
不
妨
设
a
x
=
1
+
t
b
代码意图转化为：\\ \begin{aligned} &已知：\begin{cases} (b\,\%\,a)*x_1 &= 1 (mod \,\,a) \quad\quad\quad (1) \\ a*y_1 &= 1(mod \,\, (b\%a)) \quad (2) \\ \end{cases} \\ &求得：\begin{cases} a*x = 1(mod \,\,b) \quad (3)\\ b*y = 1(mod \,\,a) \quad (4)\\ \end{cases} \quad 其中，\begin{cases} x = y_1 – (b/a)x_1 \quad(5)\\ y = x_1 \quad(6) \end{cases} \\ \\ &设\,b=ka+r \,\,\,(7)\,,\,r=b\%a \,\,\,(8)\,,\,由于by=(ka+r)y=ry=rx_1=1(mod \,\,a)\,,\,可知由(1),(6)可推出(4)。 \\\\ &由(1)不妨设\,\,rx_1=1+da \,\,\,(9)\,,\,由(2)不妨设\,\,ay_1 = 1+pr\,\,\,(10)\,,\,由(3)不妨设\,\,ax=1+tb\,\,\, \end{aligned}
代
码
意
图
转
化
为
：
已
知
：
{
(
b
%
a
)
∗
x
1
a
∗
y
1
=
1
(
m
o
d
a
)
(
1
)
=
1
(
m
o
d
(
b
%
a
)
)
(
2
)
求
得
：
{
a
∗
x
=
1
(
m
o
d
b
)
(
3
)
b
∗
y
=
1
(
m
o
d
a
)
(
4
)
其
中
，
{
x
=
y
1
−
(
b
/
a
)
x
1
(
5
)
y
=
x
1
(
6
)
设
b
=
k
a
+
r
(
7
)
,
r
=
b
%
a
(
8
)
,
由
于
b
y
=
(
k
a
+
r
)
y
=
r
y
=
r
x
1
=
1
(
m
o
d
a
)
,
可
知
由
(
1
)
,
(
6
)
可
推
出
(
4
)
。
由
(
1
)
不
妨
设
r
x
1
=
1
+
d
a
(
9
)
,
由
(
2
)
不
妨
设
a
y
1
=
1
+
p
r
(
1
0
)
,
由
(
3
)
不
妨
设
a
x
=
1
+
t
b
上面写得兴起了，变得复杂了，实属不该！
这才是对的
有
解
的
正
常
的
递
推
终
止
条
件
为
：
r
=
0
,
a
=
1
,
x
1
=
0
,
y
1
=
1
成
立
表
达
式
：
r
x
1
+
a
y
1
=
1
构
造
y
=
x
1
,
x
=
y
1
−
k
x
1
,
b
=
k
a
+
r
,
则
：
a
x
+
b
y
=
a
(
y
1
−
k
x
1
)
+
b
x
1
=
a
y
1
+
r
x
1
=
1
可
验
证
x
,
y
分
别
为
a
模
b
的
乘
法
逆
元
，
b
模
a
的
乘
法
逆
元
。
而
通
过
数
学
归
纳
法
知
，
a
x
+
b
y
=
1
是
递
归
栈
返
回
时
每
一
层
的
性
质
。
因
此
，
递
推
公
式
成
立
。
有解的正常的递推终止条件为：r=0\,,\,a=1\,,\,x_1=0\,,\,y_1=1 \\ 成立表达式：rx_1+ay_1 = 1 \\ 构造y=x_1\,,\,x=y_1-kx_1\,,\,b=ka+r\,,\,则：\\ ax+by=a(y_1-kx_1)+bx_1=ay_1+rx_1 = 1 \\ 可验证x,y分别为a模b的乘法逆元，b模a的乘法逆元。\\ 而通过数学归纳法知，ax+by = 1 是递归栈返回时每一层的性质。\\ 因此，递推公式成立。
有
解
的
正
常
的
递
推
终
止
条
件
为
：
r
=
0
,
a
=
1
,
x
1
=
0
,
y
1
=
1
成
立
表
达
式
：
r
x
1
+
a
y
1
=
1
构
造
y
=
x
1
,
x
=
y
1
−
k
x
1
,
b
=
k
a
+
r
,
则
：
a
x
+
b
y
=
a
(
y
1
−
k
x
1
)
+
b
x
1
=
a
y
1
+
r
x
1
=
1
可
验
证
x
,
y
分
别
为
a
模
b
的
乘
法
逆
元
，
b
模
a
的
乘
法
逆
元
。
而
通
过
数
学
归
纳
法
知
，
a
x
+
b
y
=
1
是
递
归
栈
返
回
时
每
一
层
的
性
质
。
因
此
，
递
推
公
式
成
立
。
Note : 递归算法要先考虑
终止返回条件
，再考虑递推公式。
写法二：
只是函数参数传递的技巧，与写法一无太大区别
//C++:
inline long long extend_gcd(long long a, long long b, long long &x, long long &y)
{
if (a == 0 && b == 0)
return -1ll;
if (b == 0)
{
x = 1ll;
y = 0ll;
return a;
}
long long d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
简单证明：
有
解
的
正
常
的
递
推
终
止
条
件
为
：
r
=
0
,
b
=
1
,
x
1
=
1
,
y
1
=
0
成
立
表
达
式
：
r
y
1
+
b
x
1
=
1
构
造
y
=
x
1
−
k
y
1
,
x
=
y
1
,
a
=
k
b
+
r
,
则
：
a
x
+
b
y
=
a
y
1
+
b
(
x
1
−
k
y
1
)
=
b
x
1
+
r
y
1
=
1
可
验
证
x
,
y
分
别
为
a
模
b
的
乘
法
逆
元
，
b
模
a
的
乘
法
逆
元
。
而
通
过
数
学
归
纳
法
知
，
a
x
+
b
y
=
1
是
递
归
栈
返
回
时
每
一
层
的
性
质
。
因
此
，
递
推
公
式
成
立
。
有解的正常的递推终止条件为：r=0\,,\,b=1\,,\,x_1=1\,,\,y_1=0 \\ 成立表达式：ry_1+bx_1 = 1 \\ 构造y=x_1-ky_1\,,\,x=y_1\,,\,a=kb+r\,,\,则：\\ ax+by=ay_1+b(x_1-ky_1)=bx_1+ry_1 = 1 \\ 可验证x,y分别为a模b的乘法逆元，b模a的乘法逆元。\\ 而通过数学归纳法知，ax+by = 1 是递归栈返回时每一层的性质。\\ 因此，递推公式成立。
有
解
的
正
常
的
递
推
终
止
条
件
为
：
r
=
0
,
b
=
1
,
x
1
=
1
,
y
1
=
0
成
立
表
达
式
：
r
y
1
+
b
x
1
=
1
构
造
y
=
x
1
−
k
y
1
,
x
=
y
1
,
a
=
k
b
+
r
,
则
：
a
x
+
b
y
=
a
y
1
+
b
(
x
1
−
k
y
1
)
=
b
x
1
+
r
y
1
=
1
可
验
证
x
,
y
分
别
为
a
模
b
的
乘
法
逆
元
，
b
模
a
的
乘
法
逆
元
。
而
通
过
数
学
归
纳
法
知
，
a
x
+
b
y
=
1
是
递
归
栈
返
回
时
每
一
层
的
性
质
。
因
此
，
递
推
公
式
成
立
。
算法实现
对扩展欧几里得算法返回的结果加以判断处理
//C++:
inline long long extend_gcd(long long a, long long b, long long &x, long long &y)
{
if (a == 0 && b == 0)
return -1ll;
if (b == 0)
{
x = 1ll;
y = 0ll;
return a;
}
long long d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
inline long long mod_reverse(long long a, long long n) // 若返回-1，则表示整数a关于模m的乘法逆元不存在
{
long long x, y, d = extend_gcd(a, n, x, y);
if (d == 1)
{
if (x % n <= 0)
return x % n + n;
else
return x % n;
}
else
return -1ll;
}
相关联想以及应用
孙子定理中用于求解一次同余组的关键因子：
结尾
孙子定理也称中国剩余定理，我为此感到骄傲和自豪，为我国古代数学文化与智慧点赞！