乘法逆元详解【费马小定理+扩展欧几里得算法】

• yangweiping2011 发布于
• 988 收藏

乘法逆元 何为乘法逆元？ 对于两个数a,pa,p若gcd(a,p)=1gcd(a,p)=1则一定存在另一个数bb，使得ab≡1(modp)ab≡1(modp)，并称此时的bb为aa关于11模pp的乘法逆元。我们记此时的bb为inv(a)inv(a)或a−1a−1。 举个例子：5×3≡1(mod14)5×3≡1(mod14)，我们称此时的33为55关于11模1414的乘法逆元。 如何求乘法逆...