用C语言编制的求模逆元的扩展欧几里德算法，只要能基本上实现这个功能就行

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

下面是一个使用C语言的实现：

intexGcd(int a,int b,int &x,int &y)

{

    if(b==0)    //当b==0时，得到解

    {

        x=1y=0

        return a

    }

    intr=exGcd(b,a%b,x,y)//递归调用自身，求解

    intt=xx=yy=t-a/b*y

    return r

}

程序如下：

#include <conio.h>

#include <stdio.h>

int ExtEnclid(int d,int f)

{

int x1,x2,x3,y1,y2,y3,t1,t2,t3,k

if(d>f) d=d+f-(d=f) //交换d和f使得d<f

x1=1,x2=0,x3=f

y1=0,y2=1,y3=d

while(1)

{

if(y3==0)

{

return 0 //没有逆元,gcd(d,f)=x3

}

if(y3==1)

{

return y2 //逆元为y2,gcd(d,f)=1

}

k=x3/y3

t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3

x1=y1,x2=y2,x3=y3

y1=t1,y2=t2,y3=t3

}

}

int main()

{

int a, n, res

printf("求 a^(-1) mod n 的值：\n")

printf("a = ")

scanf("%d", &a)

printf("n = ")

scanf("%d", &n)

res = ExtEnclid(a,n)

if (res == 0)

{

printf("Not Exist!\n")

getch()

return (0)

}

else if(res<0)

{

res = res + n

}

printf("a^(-1) mod n = %d\n", res)

getch()

return (0)

}

计算1/x mod n =x^(-1) mod n

就是求y，满足：

yx = 1 mod n

y是有限域F(n)上x的乘法逆元素

可用扩展的欧几里得算法求乘法逆元

扩展的欧几里德算法简单描述如下：

ExtendedEuclid(d,f)

1 （X1,X2,X3):=(1,0,f)

2 (Y1,Y2,Y3):=(0,1,d)

3 if (Y3=0) then return d'=null//无逆元

4 if (Y3=1) then return d'=Y2 //Y2为逆元

5 Q:=X3 div Y3

6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)

7 （X1,X2,X3):=(Y1,Y2,Y3)

8 (Y1,Y2,Y3):=(T1,T2,T3)

9 goto 3

---