两种求模m逆元的方法

• ppgetyou 发布于
• 1070 收藏

在a|b（a能整除b）的前提下，计算（b/a）mod m的时候转化为 计算（b*x）mod m ; 这时的x就是a的逆元（a模m的逆元）；                                 此时x满足  （a*x mod m == 1）；     这个x的求法有一下两种： 1）扩展欧几里得算法求解 a*x+m*y=1;  因为 a*x mod m == 1     a*x=1+m...