0x1 定义

有整数a，b，n。整数a对同余n的模反元素指满足下式的整数b：

$ a^{-1}\equiv b (\bmod n) $ 或者 $ ab \equiv 1 (\bmod n) $

整数 a 对模数 n 之模反元素存在的充分必要条件是 a 和 n 互质，若此模反元素存在，在模数 n 下的除法可以用和对应模反元素的乘法来达成，此概念和实数除法的概念相同。

0x2 求模反元素

  1. 扩展欧几里得算法

    设exgcd(a,n)为扩展欧几里得算法的函数，则可得到$ax+ny=g$，g是a,n的最大公因数。

    若 $g=1$

    则该模反元素存在，根据结果$a x+n y=1$

    在 mod n 之下，$a x+n y \equiv a x \equiv 1$，根据模反元素的定义$a \cdot a^{-1} \equiv 1$，此时x即为a关于模n的其中一个模反元素。

    事实上，$x+k n(k \in \mathbb{Z})$ 都是a关于模n的模反元素，这里我们取最小的正整数解$x \bmod n(x<n)$。

    若$g \neq 1$

    则该模反元素’‘不存在’‘。

    因为根据结果$a x+n y \neq 1$，在 mod n之下，$a x \equiv g(g<n)$不会同余1，因此满足$a \cdot a^{-1} \equiv 1$的$a^{-1}$不存在。

    demo

    已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式$a x+b y=\operatorname{gcd}(a, b)$。

    用类似辗转相除法，求二元一次不定方程$53 x+19 y=1$的整数解。

    $53=19 \times 2+15$

    $19=15 \times 1+4$

    $15=4 \times 3 +3$

    $4=3 \times 1+1$

    然后把它们改写成“余数等于”的形式

    $15=53 \times 1+19 \times (-2)$ // 式1

    $4=19 \times 1+15 \times (-1)$ // 式2

    $3=15 \times 1 +4 \times (-3)$ // 式3

    $1=4 \times 1+3 \times (-1)$

    然后把它们“倒回去”

    $1=4 \times 1+3 \times (-1)$

    $1=4 \times 1+[15 \times 1 +4 \times (-3)] \times (-1)$ //用式3

    $1=15 \times (-1) + 4 \times 4$

    $1=15 \times (-1) + [19 \times 1+15 \times (-1)] \times 4$ // 用式2

    $1=19 \times 4 + 15 \times (-5)$

    $1=19 \times 4 + [53 \times 1+19 \times (-2)] \times (-5)$ // 用式1

    $1=53 \times (-5) + 19 \times 14$

    解得：$x = -5,y = 14$

  2. 欧拉定理

    欧拉定理证明当a,n为两个互质的正整数时，则有$a^{\varphi(n)} \equiv 1(\bmod n)$，其中$\varphi(n)$为欧拉函数（小于等于n且与n互质的正整数个数）。上述结果可分解为$a^{\varphi(n)}=a \cdot a^{\varphi(n)-1} \equiv 1(\bmod n)$，其中$a^{\varphi(n)-1}$即为a关于模n之模反元素。

参考：http://abloz.com/tech/2018/08/21/modular-multiplicative-inverse/