初等数论_3 2016.4.1

• black_yu 发布于
• 1505 收藏

2.7扩展欧几里德算法的应用 （3）求解模的逆元： 例如：4关于1模7的乘法逆元为多少？ 4X≡1 mod 7 这个方程等价于求一个X和K，满足 4X=7K+1 其中X和K都是整数。 若ax≡1 mod f, 则称a关于模f的乘法逆元为x。 也可表示为ax≡1(mod f)。 当a与f互素时（即Gcd(a, f) = 1），a关于模f的乘法逆元有唯一解。 如果不互素，则无解...