最近学习了扩展欧几里得和乘法逆元的关系，在这里写一下巩固一下记忆
扩展欧几里得是什么呢，在这就不详解了，可以自行百度，主要来说，对于 求解ax ≡ 1(mod n)来说，当gcd(a,n)=1时，证明逆元存在，若不等于1，则证明逆元不存在。
那么当逆元存在时，我们要如何求它的逆元呢？
首先是扩展欧几里得定理，先将式子转换成 ax-ny = 1 的形式，然后我们要通过扩展欧几里得定律去获得它的最大公约数，还有它的一组解 X0,Y0
1 int exgcd(int a, int b, int &x, int &y) 2 { 3 if (b == 0) 4 { 5 x = 1; 6 y = 0; 7 return a; 8 } 9 10 int mod = exgcd(b, a%b, x, y); 11 int tmp = x; 12 x = y; 13 y = tmp - (a / b)*y; 14 return mod; 15 }
然后是判断
1 int Inverse_element(int a, int n) 2 { 3 int gcd, x, y; 4 gcd = exgcd(a, n, x, y); 5 cout << x << endl; 6 if (gcd == 1)return (x%n + n) % n; 7 else return -1; 8 }
当gcd == 1时 证明此方程有解，并且前面已经通过扩展欧几里得定理得出了它的一组解 X， 然后我们可以通过(x%n +n )%n 防止 x 是负数情况，保证是以正整数返回。
最后是整个代码，这样，一个简单的求逆元的程序就出来了：
1 #include<iostream> 2 #include<malloc.h> 3 #include<string> 4 #include<cmath> 5 #include<conio.h> 6 7 using namespace std; 8 9 int exgcd(int a, int b, int &x, int &y) 10 { 11 if (b == 0) 12 { 13 x = 1; 14 y = 0; 15 return a; 16 } 17 18 int mod = exgcd(b, a%b, x, y); 19 int tmp = x; 20 x = y; 21 y = tmp - (a / b)*y; 22 return mod; 23 } 24 25 int Inverse_element(int a, int n) 26 { 27 int gcd, x, y; 28 gcd = exgcd(a, n, x, y); 29 cout << x << endl; 30 if (gcd == 1)return (x%n + n) % n; 31 else return -1; 32 } 33 34 int main(int argc, const char * argv[]) 35 { 36 int a, n; 37 cin >> a >> n; 38 int mod = Inverse_element(a, n); 39 cout << mod <<endl; 40 _getch(); 41 return 0; 42 }