【 逆元 】

2019-04-13 15:26发布

定义 如果ab≡1(mod m), 则称b是a的模m逆, 记作a的模m逆是方程ax≡1(mod m)的解. 例:
求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+10 21=10*2+1 回代 1=21-10*2 1=21-(73-21*3)*2 =21-73*2+6*21 =7*21-73*2 得 21 -1 ≡7(mod73).