JAVA实现辗转相除法 欧几里得算法求逆
乘法逆元定义：
一般来讲，如果要运算加法、减法、乘法、乘方，都应该满足以下式子：
(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的乘法逆元：
运行结果：
文章图片
附录：
java实现：
package oujilide;
public class ojld {
public static intniyuan(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]+"");
【JAVA实现辗转相除法 欧几里得算法求逆】}
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);
}
}
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 事件代理
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Java|Java OpenCV图像处理之SIFT角点检测详解
- Node.js中readline模块实现终端输入
- java中如何实现重建二叉树