模反元素

-- TOC --

模反元素也称为模倒数，或者模逆元。

如果两个正整数a和n互质，那么一定存在整数b，使得：

$$ab\equiv1\pmod{n}$$

a和n互质，a不能被n整除，当找到了模反元素b，计算 $ab-1$ ，就可以被n整除了，b就是a的模反元素。

欧拉定理可以证明模反元素必然存在：

$a^{\psi(n)}=a \times a^{\psi(n)-1}\equiv1\pmod n$

a的模反元素不止一个，因为：

$a \times (b\pm{kn})\equiv1\pmod n$

b加减n的整数倍，得到的数都是a的模反元素。

也可以这样来理解如何求得模反元素，列式：

$ax + kn = 1$

x是a的模反元素，是要求的未知数，kn表示n的k倍，计算上式，只需要枚举k，就可以得到一组x。

-- EOF --

-- MORE --