JAVA实现辗转相除法欧几里得算法求逆

Love The Way You Lie 2022-04-18 05:38 251阅读 0赞

乘法逆元定义：

一般来讲，如果要运算加法、减法、乘法、乘方，都应该满足以下式子：

(a+b)%c=(a%c+b%c)%c(a+b)%c=(a%c+b%c)%c

(a−b)%c=(a%c−b%c)%c(a−b)%c=(a%c−b%c)%c

(a⋅b)%c=(a%c⋅b%c)%c(a·b)%c=(a%c·b%c)%c

ab%p=(a%p)b%pab%p=(a%p)b%p

然而这里出现了一个问题：

如果是除法，并不满足(a/b)%c=(a%c/b%c)%c(a/b)%c=(a%c/b%c)%c，不信你代个数试试：

(6/3)%3=2≠(6%3/3%3)%3=RuntimeError(6/3)%3=2≠(6%3/3%3)%3=RuntimeError

那怎么实现对除法的取余呢？

这里就引入乘法逆元这个东西。

他可以达到这样的效果：

(a/b)%k=(a⋅c)%k(a/b)%k=(a·c)%k

你可以将它简单地理解为类似于倒数的东西，只不过是再对倒数取余而已，即：

(b⋅c)%k=1(b·c)%k=1

所以注意，逆元是针对一个数而言的，并不是针对一个表达式。

**求法**

使用扩展欧几里德算法，但是好像只能在所求的数和取余的数互质才行。

因为：

(b⋅c)%k=1(b·c)%k=1

所以我们可以得到

b⋅c+n⋅k=1b·c+n·k=1

所以只有在bb和kk互质的情况下，才能得到：

b⋅c+n⋅k=gcd(b,k)b·c+n·k=gcd(b,k)

然后用这个方程求解出cc的值，就是所求的乘法逆元。

**求79关于3220的乘法逆元：**

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70][]

**附录：**

java实现：

**package** oujilide;

**public** **class** ojld \{

**public** **static** **int**  niyuan(**int** a,**int** b)  //求79关于模3220的乘法逆元

\{

**int**\[\] m=\{1,0,a\};

**int**\[\] n=\{0,1,b\};

**int**\[\] temp=**new** **int**\[3\];

**int** q=0;  //初始化

**boolean** flag=**true**;

**while**(flag)

\{

q=m\[2\]/n\[2\];

**for**(**int** i=0;i<3;i\++)

\{

temp\[i\]=m\[i\]-q\*n\[i\];

m\[i\]=n\[i\];

n\[i\]=temp\[i\];

System.***out***.print(temp\[i\]+"   ");

\}

System.***out***.println();

**if**(n\[2\]==1)

\{

**if**(n\[1\]<0)

n\[1\]=n\[1\]+a;

**return** n\[1\];

\}

**if**(n\[2\]==0)

flag=**false**;

\}

**return** 0;

\}

**public** **static** **void** main(String\[\] args) \{

**int** result = *niyuan*(3220,79);

System.***out***.println();

System.***out***.println("79关于3220的逆元为："\+result);

\}

\}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70]: /images/20220418/ad313f1ef171487998b18749857426ea.png

发表评论取消回复

表情：

评论列表（有 0 条评论，251人围观）

还没有评论，来说两句吧...

相关阅读

相关求最大公约数和最小公倍数---辗转相除法(欧几里得算法)

目录一.GCD和LCM 1.最大公约数 2.最小公倍数二.暴力求解 1.最大公约数 2.最小公倍数三.辗转相除法 1.最大公约数 2.最小公倍数 --

太过爱你忘了你带给我的痛/ 2024年03月25日 13:56/ 0 赞/ 88 阅读

相关欧几里得算法（辗转相除法）

算法是程序的灵魂，不懂算法的程序员不是一个合格的程序员。源自LeetCode上的一道算法题，说实话，我已经忘记欧几里得算法是怎么实现的了。。。简介：欧几里得算法

迈不过友情╰/ 2023年07月13日 15:28/ 0 赞/ 120 阅读

相关欧几里德算法求最大公约数（辗转相除法）

//递归版本 include<stdio.h> int gcd(int a,int b) { if(b==0) {

r囧r小猫/ 2023年02月17日 06:19/ 0 赞/ 114 阅读

相关证明辗转相除法(欧几里德算法)

定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。证明： gcd(

刺骨的言语ヽ痛彻心扉/ 2023年01月03日 14:28/ 0 赞/ 201 阅读

相关欧几里得算法(辗转相除法)--Java实现

欧几里得算法(辗转相除法)–Java实现版本一、非递归版本 static int gcd(int a,int b) { wh

迷南。/ 2022年10月28日 03:42/ 0 赞/ 166 阅读

相关求最大公约数-辗转相除法-欧几里德算法

这是一个 Python 写的求最大公约数的算法。 a = 12 b= 42 def find_divisor(a,b):

傷城~/ 2022年08月09日 12:45/ 0 赞/ 272 阅读

相关欧几里得辗转相除法

欧几里德算法又称辗转相除法，是用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式 gcd (a, b) = gcd (b, a mod b)。(gr

秒速五厘米/ 2022年05月28日 05:07/ 0 赞/ 188 阅读

相关 JAVA实现辗转相除法欧几里得算法求逆

乘法逆元定义：一般来讲，如果要运算加法、减法、乘法、乘方，都应该满足以下式子： (a+b)%c=(a%c+b%c)%c(a+b)%c=(a%c+b%c)%c

Love The Way You Lie/ 2022年04月18日 05:38/ 0 赞/ 252 阅读

相关欧几里得算法(辗转相除法）求最大公约数代码

求解最大公约数依据如下定理：gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)；两个整数的最大公约数等于其中较小的那个数

短命女/ 2022年04月17日 05:07/ 0 赞/ 387 阅读

相关【算法】欧几里德算法(辗转相除法)求最大公约数

> 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。 gcd(a,b) =

浅浅的花香味﹌/ 2022年04月10日 07:16/ 0 赞/ 206 阅读