admin
2025-12-17 01:37:11
目录
前言一、逆元的概念1、基本定义示例 1：
a
=
3
,
m
=
7
a = 3, m = 7
a=3,m=7示例 2：
a
=
2
,
m
=
5
a = 2, m = 5
a=2,m=5
2、乘法逆元有什么用3、相关性质
二、求解逆元的方法1、费马小定理求乘法逆元定义费马小定理求逆元的方法总结模板题
2、扩展欧几里得算法求逆元定义扩展欧几里得算法求逆元的方法总结模板题
3、递推公式求逆元定义递推公式的推导示例
总结
前言
首先，下面讨论的是数论相关内容。主要研究对象是非负整数。其次，博客不对一些定理进行数学推理，只阐述相关结论或者性质。另外，涉及到相关代码演示，使用的是Java语言。
一、逆元的概念
1、基本定义
倒数的概念相信大家都很了解，给定两个数字，
a
和
b
a和b
a和b若：
a
×
b
=
=
1
a\times b==1
a×b==1 那么
a
和
b
a和b
a和b互为倒数。
逆元和倒数的概念类似。不过逆元是模运算上“倒数”的概念。 在模m的情况下，给定一个整数
a
a
a，存在另一个整数
b
b
b，使得：
a
×
b
≡
1
(
m
o
d
m
)
a \times b \equiv 1 \pmod{m}
a×b≡1(modm) 即，
(
a
×
b
)
(
m
o
d
m
)
=
1
(a \times b) \pmod m = 1
(a×b)(modm)=1 ， 那么b就是a在模m下的乘法逆元。 和倒数的概念类似，a和b互为乘法逆元，但必须是在模m的条件下成立！
举几个栗子，说明什么是逆元：
示例 1：
a
=
3
,
m
=
7
a = 3, m = 7
a=3,m=7
我们需要找到一个整数
b
b
b，使得：
3
×
b
≡
1
(
mod
7
)
3 \times b \equiv 1 \ (\text{mod} \ 7)
3×b≡1 (mod 7)
尝试不同的
b
b
b 值：
3
×
1
=
3
≡
3
(
mod
7
)
3 \times 1 = 3 \equiv 3 \ (\text{mod} \ 7)
3×1=3≡3 (mod 7)
3
×
2
=
6
≡
6
(
mod
7
)
3 \times 2 = 6 \equiv 6 \ (\text{mod} \ 7)
3×2=6≡6 (mod 7)
3
×
3
=
9
≡
2
(
mod
7
)
3 \times 3 = 9 \equiv 2 \ (\text{mod} \ 7)
3×3=9≡2 (mod 7)
3
×
4
=
12
≡
5
(
mod
7
)
3 \times 4 = 12 \equiv 5 \ (\text{mod} \ 7)
3×4=12≡5 (mod 7)
3
×
5
=
15
≡
1
(
mod
7
)
3 \times 5 = 15 \equiv 1 \ (\text{mod} \ 7)
3×5=15≡1 (mod 7)
因此，
b
=
5
b = 5
b=5 是
3
3
3 在模
7
7
7 下的逆元，因为
3
×
5
≡
1
(
mod
7
)
3 \times 5 \equiv 1 \ (\text{mod} \ 7)
3×5≡1 (mod 7)。
示例 2：
a
=
2
,
m
=
5
a = 2, m = 5
a=2,m=5
我们需要找到
b
b
b，使得：
2
×
b
≡
1
(
mod
5
)
2 \times b \equiv 1 \ (\text{mod} \ 5)
2×b≡1 (mod 5)
尝试不同的
b
b
b 值：
2
×
1
=
2
≡
2
(
mod
5
)
2 \times 1 = 2 \equiv 2 \ (\text{mod} \ 5)
2×1=2≡2 (mod 5)
2
×
2
=
4
≡
4
(
mod
5
)
2 \times 2 = 4 \equiv 4 \ (\text{mod} \ 5)
2×2=4≡4 (mod 5)
2
×
3
=
6
≡
1
(
mod
5
)
2 \times 3 = 6 \equiv 1 \ (\text{mod} \ 5)
2×3=6≡1 (mod 5)
因此，
b
=
3
b = 3
b=3 是
2
2
2 在模
5
5
5 下的逆元，因为
2
×
3
≡
1
(
mod
5
)
2 \times 3 \equiv 1 \ (\text{mod} \ 5)
2×3≡1 (mod 5)。
2、乘法逆元有什么用
我们知道，在数学的模运算中，参数必须是整数（即使在许多编程语言中支持对浮点数进行模运算），因此在模运算中可能出现这种冲突：
3
/
2
≡
?
(
m
o
d
107
)
3 /2 \equiv ? \pmod{107}
3/2≡?(mod107) 3
÷
2
=
1.5
\div2=1.5
÷2=1.5是一个小数，小数不能进行模运算啊。因此我们需要想办法把
÷
2
\div2
÷2等价替换成其他参数，使得
(
3
÷
2
)
(3\div2)
(3÷2)这个整体是一个整数，然后再进行模
107
107
107. 而乘法逆元就可以完美做到这一点。
根据乘法逆元的定义，我们设
a
a
a是
2
2
2在模m的情况下的乘法逆元：
a
×
2
≡
1
(
m
o
d
107
)
a \times 2 \equiv 1 \pmod{107}
a×2≡1(mod107) 式子两边同时除以2：
a
≡
1
/
2
(
m
o
d
107
)
a \equiv 1/2 \pmod{107}
a≡1/2(mod107) 这时，我们就可以把原式中【
3
/
2
≡
?
(
m
o
d
107
)
3 /2 \equiv ? \pmod{107}
3/2≡?(mod107)】 的1/2替换成
a
a
a：
3
×
a
≡
?
(
m
o
d
107
)
3 \times a \equiv ? \pmod{107}
3×a≡?(mod107) 根据计算，2在模107下的乘法逆元是54，所以
3
×
54
≡
?
(
m
o
d
107
)
→
162
≡
55
(
m
o
d
107
)
3 \times 54 \equiv ? \pmod{107} \rightarrow 162 \equiv 55 \pmod{107}
3×54≡?(mod107)→162≡55(mod107) 余数55就计算出来了。
3、相关性质
只有当a和m的最大公约数等于gcd(a,m)=1，a在模m的情况下的乘法逆元b才存在。如果在模m的情况下，a的乘法逆元b存在，那么整数b一定是唯一的。
二、求解逆元的方法
1、费马小定理求乘法逆元
定义
小定理，快速理解：
费马小定理是数论中的一个重要定理，用于求解模运算下的逆元。对于一个质数 p ，如果 ( a ) 是一个整数且与 ( p ) 互质（即 gcd(a, p) = 1 ），费马小定理指出：
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1} \equiv 1 \pmod{p}
ap−1≡1(modp)
这就是费马小定理。
费马小定理求逆元的方法
根据这个定理我们可以求出，a在模p下的逆元，因为上述式子可以被改写成这样：
a
⋅
a
p
−
2
≡
1
(
m
o
d
p
)
a \cdot a^{p-2} \equiv 1 \pmod{p}
a⋅ap−2≡1(modp)
根据乘法逆元的定义，ap-2模p 就是
a
a
a在模
p
p
p的情况下的乘法逆元。
总结
当我们要求一个整数a在模p的情况下的乘法逆元，并且p是质数，gcd(a,p)=1，那么可以运用费马小定理求解，ap-2模p 就是a在模p的情况下的乘法逆元。 时间复杂度是
O
(
log
(
p
)
)
O(\log(p))
O(log(p)) ，因为可以使用快速幂去求解ap-2 。
模板题
费马小定理求逆元
AC代码：
import java.util.Scanner;
public class Test{
/**
* 计算a^(p-2) （mod m）
* */
private static int pow(long base,long x,long m){
long result=1;
while(x>0){
if((x&1)==1){
result*=base;
result%=m;
}
base*=base;
base%=m;
x>>=1;
}
return (int)result;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int p=sc.nextInt();
int ans=pow(n,p-2,p);
System.out.println(ans);
}
}
2、扩展欧几里得算法求逆元
注意：观看这里，建议先了解裴蜀定理，了解定义即可。
定义
扩展欧几里得算法不仅可以用来计算两个数的最大公约数，还可以找到这两个数的线性组合。例如，对于给定的两个整数
a
a
a 和
b
b
b，扩展欧几里得算法可以找到整数
x
x
x 和
y
y
y 使得：
a
×
x
+
b
×
y
=
gcd
(
a
,
b
)
a \times x + b \times y = \text{gcd}(a, b)
a×x+b×y=gcd(a,b)
当
a
a
a 和
m
m
m 互质（即
gcd
(
a
,
m
)
=
1
\text{gcd}(a, m) = 1
gcd(a,m)=1）时，可以找到整数
x
x
x 使得：
a
×
x
≡
1
(
m
o
d
m
)
a \times x \equiv 1 \pmod{m}
a×x≡1(modm)
这意味着
x
x
x 就是
a
a
a 在模
m
m
m 下的乘法逆元！
扩展欧几里得算法求逆元的方法
如果我们要计算a在模m的情况下的乘法逆元：
使用扩展欧几里得算法计算
a
a
a 和
m
m
m 的最大公约数
gcd
(
a
,
m
)
\text{gcd}(a, m)
gcd(a,m)。如果
gcd
(
a
,
m
)
≠
1
\text{gcd}(a, m) \neq 1
gcd(a,m)=1，则
a
a
a 在模
m
m
m 下的逆元不存在。
如果
gcd
(
a
,
m
)
=
1
\text{gcd}(a, m) = 1
gcd(a,m)=1，扩展欧几里得算法会找到整数
x
x
x 和
y
y
y，使得：
a
×
x
+
m
×
y
=
g
c
d
(
a
,
m
)
=
1
(
m
o
d
m
)
a \times x + m \times y = gcd(a,m)=1 \pmod{m}
a×x+m×y=gcd(a,m)=1(modm) 进一步改写：
a
×
x
+
m
×
y
=
1
(
m
o
d
m
)
a \times x + m \times y= 1 \pmod{m}
a×x+m×y=1(modm) 因为右边第二项模m为0，所以在进一步改写：
a
×
x
=
1
(
m
o
d
m
)
a \times x = 1 \pmod{m}
a×x=1(modm) 根据这个等式，便得出
a
×
x
≡
1
(
m
o
d
m
)
a \times x \equiv 1 \pmod{m}
a×x≡1(modm)，因此
x
x
x 就是
a
a
a 在模
m
m
m 下的乘法逆元。 如果对x的求解方式不太了解，请看裴蜀定理详细介绍 中的二.2节，包含证明以及求x得公式。
总结
当我们要求一个整数a在模p的情况下的乘法逆元，并且gcd(a,p)=1，那么可以使用扩展欧几里得算法求解。 裴蜀定理中得系数x，就是我的答案（当然如果x是负数，或者是p的倍数，进行模运算的处理即可，具体可以看模板题的操作）
模板题
exgcd求逆元
AC代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static class ResultGCD{
int x;
int y;
int gcd;
public ResultGCD(int xx,int yy,int gg){
x=xx;
y=yy;
gcd=gg;
}
}
private static ResultGCD exGcd(int a,int b){
if(b==0)return new ResultGCD(1,0,a);
ResultGCD result=exGcd(b,a%b);
int gcd=result.gcd;
int xx=result.x;
int yy=result.y;
int x=yy;
int y=xx-(a/b)*yy;
return new ResultGCD(x,y,gcd);
}
private static int getInvers(int a,int m){
ResultGCD ans=exGcd(a,m);
if(ans.gcd==1){
//特殊处理
return (ans.x%m+m)%m;
}else return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
for(int i=0;i int a=scan.nextInt(); int b=scan.nextInt(); int ans=getInvers(a,b); System.out.println(ans); } scan.close(); } } 3、递推公式求逆元 递推公式法是一种求解连续整数逆元的快速方法，适用于模 p p p 是质数的情况。 定义 递推公式法适用于要求从 1 1 1 到 n n n 的所有整数在模 p p p 下的逆元，其中 p p p 是质数。通过递推，我们可以快速地求得这些逆元。递推公式如下： inv [ i ] = ( p − p / i ) × inv [ p m o d i ] ( m o d p ) \text{inv}[i] = (p - p / i) \times \text{inv}[p \bmod i] \pmod{p} inv[i]=(p−p/i)×inv[pmodi](modp) inv[i] = (p - (p / i) * inv[p % i] % p) % p; 其中， inv [ i ] \text{inv}[i] inv[i] 表示整数 i i i 在模 p p p 下的乘法逆元， p p p 是质数。 递推公式的推导 假设我们已经知道了 1 , 2 , … , i − 1 1, 2, \dots, i-1 1,2,…,i−1 的逆元，接下来我们来求 i i i 的逆元。 我们可以通过以下关系得到： 根据扩展欧几里得原理，可以得到： i × inv [ i ] ≡ 1 ( m o d p ) i \times \text{inv}[i] \equiv 1 \pmod{p} i×inv[i]≡1(modp) 可以重写为： i × inv [ i ] + p × k = 1 i \times \text{inv}[i] + p \times k = 1 i×inv[i]+p×k=1 通过递推可以求出所有整数的逆元。 示例 假设我们要找出从 1 1 1 到 6 6 6 在模 7 7 7 下的逆元： 使用递推公式，可以得出： inv [ 1 ] = 1 \text{inv}[1] = 1 inv[1]=1 inv [ 2 ] = 4 \text{inv}[2] = 4 inv[2]=4 inv [ 3 ] = 5 \text{inv}[3] = 5 inv[3]=5 inv [ 4 ] = 2 \text{inv}[4] = 2 inv[4]=2 inv [ 5 ] = 3 \text{inv}[5] = 3 inv[5]=3 inv [ 6 ] = 6 \text{inv}[6] = 6 inv[6]=6 这样，我们就可以通过递推公式快速地求出一系列整数的逆元。 总结 对于求解逆元的问题，我们有三种常用的方法： 费马小定理，适用于模数是质数的情况。扩展欧几里得算法，适用于任意模数且 a a a 和 m m m 互质的情况。（这也是乘法逆元存在得前提）递推公式法，适用于连续整数在模质数 p p p 下的逆元求解。 根据实际应用场景，可以选择合适的方法来求解逆元，以简化计算过程并提高效率。 完