每個數a均有唯一的與之對應的乘法逆元x，使得ax≡1(mod n) ， 一個數有逆元的充分必要條件是gcd(a,n)=1，此時逆元唯一存在 。

逆元的含義：模n意義下，1個數a如果有逆元x，那么除以a相當于乘以x。

逆元的定義：定義：正整數 a, n，如果有 ax ≡ 1(mod n)，則稱 x 的最小正整數解為 a 模 n的逆元。

為什么要有乘法逆元呢？

當我們要求(a/b) mod p的值，且a很大，大到會溢出；或者說b很大，達到會爆精度。無法直接求得a/b的值時，我們就要用到乘法逆元。

求證：設k為b關于p的乘法逆元，證明(a/b)%m=(a*k)%m?

我們可以通過求b關于p的乘法逆元k，將a乘上k再模p，即(a*k) mod p。其結果與(a/b) mod p等價。

證：

根據b*k≡1 (mod p)有b*k=p*x+1。

k=(p*x+1)/b。

把k代入(a*k) mod p，得：

(a*(p*x+1)/b) mod p

=((a*p*x)/b+a/b) mod p

=[((a*p*x)/b) mod p +(a/b)] mod p

=[(p*(a*x)/b) mod p +(a/b)] mod p

//p*[(a*x)/b] mod p=0

所以原式等于：(a/b) mod p

更簡單的證明：

a/b mod p = ?a* (b*b^(-1) ) /b =a*b^(-1);

一、循環找解法

給定模m和需要求逆的數x，直接暴力枚舉1~m-1

檢查是否有x*i=1(mod m)

這種算法可以應用與寫暴力、對拍、模數較小,求逆次數少的情況

時間復雜度O(m)

#include

#include

using namespace std;

int main()

{

int n,m;

cin>>n>>m;

for(int i=1;i

if(i*n%m==1) {

printf("%d\n",i);

break;

}

}

return 0;

}

二、擴展歐幾里得算法

給定模數m，求a的逆元相當于求解ax=1(mod m)

這個方程可以轉化為ax-my=1

然后套用求二元一次方程的方法，用擴展歐幾里得算法求得一組x0,y0和gcd

檢查gcd是否為1

gcd不為1則說明逆元不存在

若為1，則調整x0到0~m-1的范圍中即可

( 用我自己的話解釋一下，①：extgcd 目的 求 x ,y ； ②：逆元 目的 求 x； ?③：?so 用extgcd 來求逆元 )

一個數有逆元的充分必要條件是gcd(a,n)=1，如果gcd(a,n)>1,則不存在逆元：比如：18 12

#include

#include

using namespace std;

int exgcd(int a,int b,int &x,int &y)

{

if(b==0) {

x=1,y=0;

return a;

}

int r = exgcd(b,a%b,x,y);

int t = x;

x = y;

y = t - a/b*y;

return r;

}

int inv(int n,int m)

{

int x,y;

int ans = exgcd(n,m,x,y);

if(ans == 1)

return (x%m+m)%m;

//定義：正整數 a, n，如果有 ax ≡ 1(mod n)，則稱 x 的最小整數解為 a 模 n的逆元。

else

return -1;

}

int main()

{

int n,m;

cin>>n>>m;

int ans = inv(n,m);

ans == -1 ? cout<

return 0;

}

/*

intput:

5 7

22 29

100 97

18 12

output:

3

4

65

沒有逆元

*/

三、費馬小定理及歐拉定理

四、O(n)求1~n逆元表

(這個寫的不是很詳細，具體看那個鏈接)

ps:

a與b對模m同余，記為a≡b(mod m)

ax≡1(mod p) 讀作：a關于模p的乘法逆元。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的逆元java_逆元 - 阿聊 - 博客园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。