如果有逆元,请用扩展欧几里得算法求出此乘法逆元;如果没有,请求出m和n,使得(a, b) = ma + nb。
时间: 2024-05-27 07:14:18 浏览: 100
使用扩展欧几里得算法求乘法逆元
3星 · 编辑精心推荐
如果有乘法逆元,假设a关于模数m的乘法逆元为a',则有aa'≡1(mod m),即aa'+km=1,用扩展欧几里得算法求解此方程即可得到a'。如果没有乘法逆元,则需要求出m和n使得(a, b) = ma nb。这是一个裴蜀定理的应用,裴蜀定理指出,对于任意两个整数a和b,存在整数x和y,使得它们的最大公约数等于ax+by。因此,可以使用扩展欧几里得算法求解ax+by=(a, b),即可得到m和n。
阅读全文