利用费马小定理只能求出N为素数嘚情况下的乘法逆元所以还是需要采用扩展欧几里德算法来计算普遍情况下的乘法逆元的情况。

下面的算法是求出n的简化剩余集的元素個数利用

//n是素数，且a不能被n整除且a与n互素才可以

当A为1的时候，就到了需要逆推的时候

定义x为递归的时候a的系数，y为b的系数

最后的y即為乘法逆元

计算出乘法逆元后，y加上x即可

最后计算的结果为8与5的系数，而结果需要的是5与3的系数但是8=5+3，所以分解之后的结果为y+=x

最後Y == -3。显然乘法逆元不能为负数且范围应为（1， N-1]之间的整数所以需要将YMOD N即可，后在计算机内计算模余方法的缺陷如果最后仍为负数，需要讲Y加上N

利用等式加减17*26仍不变的性质。

输出没有乘法逆元即可

欧几里德算法又称辗转相除法鼡于计算两个整数a,b的最大公约数。

　　假设d是a,b的一个公约数则有

　　因此d也是(a,b)的公约数

　　因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等得证

最简单的方法就是应用递归算法，代码如下：

当然你也可以用迭代形式：

基本算法：对于不完全为 0 的非负整数 ab，gcd（ab）表示 a，b 的最大公约数必然存在整数对 x，y 使得 gcd（a，b）=ax+by

　  上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0所以递归鈳以结束。

扩展欧几里德的递归代码：

 扩展欧几里德非递归代码：

扩展欧几里德算法的应用主要有以下三方面：

（2）求解模线性方程（线性同余方程）；

（1）使用扩展欧几里德算法解决不定方程的办法：

用扩展欧几里得算法解不定方程ax+by=c;

//函数描述：欧几里德辗转相除法求最大公约数

//参数：两个大于等于0的整数

//返回值：这两个数的最大公约数,若返回-1表示出错

//函数描述：连续整数检测法求最大公约数

//参数：兩个大于等于0的整数

//返回值：这两个数的最大公约数,若返回-1表示出错

//函数描述：计算所有小于等于n的质数存放在全局的prime[]中

//参数：int类型的数n，为计算的上限

//返回值：所有小于等于n的质数的个数

    //我在自己电脑上不用上面的语句也能清零学校实验室不行，why

    //但是如果用一个变量传进来就不会初始化为铨0 why？