求逆元

定义如果ab≡1(modm),则称b是a的模m逆,记作a的模m逆是方程ax≡1(modm)的解.例：求5的模7逆做辗转相除法,求得整数b,k使得5b+7k=1,则b是5的模7逆.计算如下:7=5+2,5=2×2+1.回代1=5-2×2=5-2×(7-5)=3×5-2×7,得5-1≡3(mod7).例：求21的模73逆做辗转相除法,求得整数b,k使得21b+73k=1,则b是21的模73逆.计算如下:73=21*3+1021=10*2+1回代1=21-10*21=21-（73-21*3）*2=21-73*2+6*21=7*21-73*2得21-1≡7(mod73).