1.乘法逆元 a*x = 1 mod n，那么x就是a的乘法逆元模n。 即a*x = k*n + 1, 根据扩展的欧几里得定理，a存在乘法逆元模n 的 充要条件是 a和n互质。 如何求解逆元？ 不断用除数与余数做除法，直到得到余数1为止，然后再倒推一次。 比如求997 模 126的乘法逆元。 997 = 126 * 7 + 115 126 = 115 * 1 + 11 115 = 11 * 10 + 5 11 = 5 * 2 + 1结束。 1 = 11 - 5 * 2 1 = 11 - (115 - 11 * 10) * 2 = 21 * 11  - 115 * 2 1 = 21 * (126 - 115) - 115 = 21 * 126 - 23 * 115 1 = 21 * 126 - 23 * (997 - 126 * 7) = 182 * 126 - 23 * 997
所以126^-1 =182 mod 997, 997^-1 = -23 = 126 - 23 = 103 mod 126.
还有一种办法，根据费马小定理，若a,p互质，则a^(p-1) = 1 mod p，那么a^-1= a^(p-2) mod p。 2. CRT： 如果m1和m2互质，假设有一个数x， x = a1 mod m1 x = a2 mod m2 . k1 * m1 + a1 = a2 mod m2, k1 = (a2 - a1) * m1^-1 mod m2，因此看k1可解，x也可解。 CRT的含义是如果不知道x但是知道x模互质的两个数的余数，就可以得到x。