扩展的欧几里得算法求逆元就是计算乘法逆元,比如3mod8的乘法逆元为3是如何用欧几里得算法计算的呢,

Question

扩展的欧几里得算法求逆元
就是计算乘法逆元,比如3mod8的乘法逆元为3
是如何用欧几里得算法计算的呢,

Answer 1

数对 x,y ,使得 gcd（a,b）=ax+by.
c++语言实现
#include
#include
using namespace std;
int x,y,q;
void extend_Eulid(int a,int b)
{
if(b == 0){
x = 1;y = 0;q = a;
}else{
extend_Eulid(b,a%b);
int temp = x;
x = y;
y = temp - a/b*y;
}
}
int main()
{
int a,b;
cin>>a>>b;
extend_Eulid(a,b);
printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
return 0;
}
你给的题目实际上就是： 给定 a 和b.
a 要有逆元 , 那么gcd（ a , b ) = 1
假设a的逆元 为x , 那么就有 a * x mod b = 1
也就是 a * x + b * y = 1
上面的程序中输入a和b就可以求出对应的x和y.
其中 x 就是 a的逆元