数论 之 乘法逆元介绍（扩展欧几里得算法求解乘法逆元）
1.扩展欧几里得： 已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满贝祖等式：。 2.乘法逆元：ax≡1 (mod p) 这个等式可以描述为： a乘一个数x并模p等于1，即 a%p*x%p=res,res%p=1;看上去就是同余定理的一个简单等式。 逆元x可以描...
