algorithm-math-modular-inverse
逆元
费马小定理和逆元
在模运算中，逆元是一个非常重要的概念。如果 aaa 和 MODMODMOD 互质（即它们的最大公约数是 1），那么 aaa 在模 MODMODMOD 下的逆元 bbb 满足：
ab≡1(modMOD)ab \equiv 1 \pmod{MOD}
ab≡1(modMOD)
逆元实质上是乘法操作的“撤销”。在模 MODMODMOD 算术中，逆元使我们能够通过乘以逆元来“消除”一个数的影响，从而简化计算。
费马小定理告诉我们如何快速找到逆元，费马小定理是关于素数的一个定理，它提供了一种快速计算幂模的方法。如果 ppp 是一个素数，且 aaa 不是 ppp 的倍数，那么 ap−1a^{p-1}ap−1 被 ppp 除的余数总是 1。用数学语言来描述就是：
ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}
ap−1≡1(modp)
a∗ap−2≡1(modp)a * a^{p-2} \equiv 1 \pmod{p}
a∗ap−2≡1(modp)
a≡1/ap−2(modp)a \equiv 1 / a^{p-2} \pmod{p}
a≡1/a ...