欧几里得算法

欧几里得算法，也叫辗转相除，简称 gcd，用于计算两个整数的最大公约数

　　定义 gcd(a,b) 为整数 a 与 b 的最大公约数

给定整数a和b，且b>0，重复使用带余除法，即每次的余数为除数去除上一次的除数，直到余数为0，这样可以得到下面一组方程：
a = bq1+r1, 0 < r1 <b,
b = r1q2+r2, 0 < r2 < r1,
r1 = r2q3+r3, 0 < r3 < r2,
……
rj-1 = rjqj+1
最后一个不为0的余数rj就是a和b的最大公因子

求gcd (1970，1066)
用欧几里德算法的计算过程如下：
1970＝1×1066+904
1066＝1×904+162
904＝5×162+94
162=1×94+68
94＝1×68+26
68＝2×26+16
26＝1×16+10
16＝1×10+6
10＝1×6+4
6=1×4+2
4＝2×2+0
因此gcd (1970，1066) = 2

 扩展欧几里得算法

1.能够确定两个正整数的最大公约数
2.如果这两个正整数互素（互质），还能确定他们的逆元

如果整数n≥1，且gcd(a,n)=1,那么a有一个模n的乘法逆元a-1。即对小于n的正整数a，存在一个小于n的整数a，存在一个小于n的整数a-1，使得a * a^-1≡1 mod n。

 （1）1234 mod 4321 用扩展欧几里德算法的计算过程如下：

- 1082 =3239 mod 4321,所以逆元是 3239

（2）24140 mod 40902

无逆元