java实现求a的逆元x(附完整源码)
时间: 2024-02-06 18:10:16 浏览: 22
求a的逆元x,是指找到一个整数x,使得 a*x ≡ 1 (mod m),其中m为模数。这个问题可以用扩展欧几里得算法来解决。
以下是Java实现代码:
```
public class InverseElement {
/**
* 求a在模m意义下的逆元x
* @param a 求逆元的数
* @param m 模数
* @return a的逆元x,如果不存在逆元则返回-1
*/
public static int getInverseElement(int a, int m) {
int[] result = new int[3];
int gcd = extGcd(a, m, result);
if (gcd != 1) {
// 不存在逆元
return -1;
} else {
return (result[0] % m + m) % m;
}
}
/**
* 扩展欧几里得算法,求ax+by=gcd(a,b)的一组解
* @param a
* @param b
* @param result 存放一组解的数组,result[0]为x,result[1]为y,result[2]为gcd(a,b)
* @return gcd(a,b)
*/
private static int extGcd(int a, int b, int[] result) {
if (b == 0) {
result[0] = 1;
result[1] = 0;
result[2] = a;
return a;
} else {
int gcd = extGcd(b, a % b, result);
int x = result[1];
int y = result[0] - (a / b) * result[1];
result[0] = x;
result[1] = y;
result[2] = gcd;
return gcd;
}
}
public static void main(String[] args) {
int a = 5;
int m = 7;
int x = getInverseElement(a, m);
if (x == -1) {
System.out.println(a + "在模" + m + "意义下不存在逆元");
} else {
System.out.println(a + "在模" + m + "意义下的逆元是:" + x);
}
}
}
```
我们可以调用getInverseElement方法来求a的逆元。如果逆元存在,那么返回逆元x;否则返回-1。在main方法中,我们以a=5,m=7为例进行测试,输出结果为:
```
5在模7意义下的逆元是:3
```
表示5在模7意义下的逆元是3。