给出乘法逆元的基本概念；利用扩展欧几里得算法编写求解乘法逆元的程序，其中输入：整数e及模n，满足e和n互素，输出：e模n的乘法n逆元d.
1)乘法逆元的基本概念
如果（e×d）≡1 mod n，则e、d互为乘法逆元
如6×20≡1 mod 119
如果一个整数e与n互素，那么它在Z n中乘法逆元，例如：Z8中：1,3,5,7有乘法逆元，2,4,6没有
2)求解乘法逆元的程序
#include <stdio.h>
#include <math.h>
int x,d,q;
void ex_Eulid(int e,int n){
if(n==0)
{
x=1;
d=0;
q=e;
}
else
{
ex_Eulid(n,e%n);
double temp=x;
x=d;
d=temp-e/n*d;
}
}
int main(){
int e,n,temp;
scanf("%d %d",&e,&n);
if(e<n)
{
temp = e;
e = n;
n = temp;
}
ex_Eulid(e,n);
printf("%d\n",d);
return 0;
}
3)程序运行结果
例1
6×20≡1 mod 119
图1 6关于模119的乘法逆元为20 例2
14 = 5*2+4
5 = 4*1+1
说明5与14互素，存在5关于14的乘法逆元
1 = 5-4 = 5-（14-5*2）= 5*3-14
因此5关于模14的乘法逆元为3
图2 5关于模14的乘法逆元为3。