本文章为乘法逆元详解。

前一到二节属于前置知识：同余。

( a + b )   m o d   m = [ ( a   m o d   m ) + ( b   m o d   m ) ]   m o d   m (a+b)\bmod m=[(a\bmod m)+(b\bmod m)]\bmod m (a+b)modm=[(amodm)+(bmodm)]modm

( a − b )   m o d   m = [ ( a   m o d   m ) − ( b   m o d   m ) + m ]   m o d   m (a-b)\bmod m=[(a\bmod m)-(b\bmod m) + m]\bmod m (a−b)modm=[(amodm)−(bmodm)+m]modm

( a × b )   m o d   m = [ ( a   m o d   m ) × ( b   m o d   m ) ]   m o d   m (a\times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m (a×b)modm=[(amodm)×(bmodm)]modm

( a ÷ b )   m o d   m ≠ [ ( a   m o d   m ) ÷ ( b   m o d   m ) ]   m o d   m (a\div b) \bmod m ≠ [(a \bmod m) \div (b \bmod m)] \bmod m (a÷b)modm=[(amodm)÷(bmodm)]modm

如： ( 12 ÷ 3 )   m o d   6 = 4 ≠ ( 12   m o d   6 ) ÷ ( 3   m o d   6 ) (12\div3) \bmod 6 = 4 ≠ (12 \bmod 6) \div (3 \bmod 6) (12÷3)mod6=4=(12mod6)÷(3mod6)

若 a ≡ b ( m o d m ) a \equiv b\pmod m a≡b(modm)，则 m ∣ ( a − b ) m|(a-b) m∣(a−b)。

同加性，若 a ≡ b ( m o d m ) a\equiv b\pmod m a≡b(modm)，则 a + c ≡ b + c ( m o d m ) a+c \equiv b+c \pmod m a+c≡b+c(modm) 。

同乘性，若 a ≡ b ( m o d m ) a \equiv b \pmod m a≡b(modm)，则 a c ≡ b c ( m o d m ) ac \equiv bc \pmod m ac≡bc(modm) 。

逆性质：若 a c ≡ b c ( m o d m ) ac \equiv bc \pmod m ac≡bc(modm) ，且 gcd ⁡ ( c , m ) = 1 \gcd(c,m)=1 gcd(c,m)=1，有 a ≡ b ( m o d m ) a \equiv b \pmod m a≡b(modm)。

证明： a c − p m = b c − q m ac-pm=bc-qm ac−pm=bc−qm ， ( a − b ) c = ( p − q ) m (a-b)c=(p-q)m (a−b)c=(p−q)m， c c c 与 m m m 互质，证明 a − b a-b a−b 为 m m m 的倍数，则 a ≡ b ( m o d m ) a \equiv b \pmod m a≡b(modm)。

同幂性：若 a ≡ b ( m o d m ) a\equiv b\pmod m a≡b(modm)，则 a c ≡ b c ( m o d m ) a^c\equiv b^c\pmod m ac≡bc(modm)。

对于任意整数 a a a 而言，如果 a a a 和 p p p 互质，存在一个整数 x x x 使得 a × x ≡ 1 ( m o d p ) a\times x \equiv 1\pmod p a×x≡1(modp) ，则有：

b ÷ a   m o d   p = b ÷ a × ( a × x )   m o d   p = b ÷ ( a × a ) × x   m o d   p = b × x   m o d   p \begin{aligned} b\div a\bmod p&=b\div a\times(a\times x)\bmod p \\&=b\div (a\times a)\times x\bmod p\\&=b\times x\bmod p \end{aligned} b÷amodp​=b÷a×(a×x)modp=b÷(a×a)×xmodp=b×xmodp​

x x x 为 a a a 在模 p p p 意义下的乘法逆元，写作 a − 1 a^{-1} a−1。

我们可以借此解决运算法则四遇到的问题。

例如： 2 × 5 ≡ 1 ( m o d 9 ) 2\times 5 \equiv 1\pmod 9 2×5≡1(mod9)，则 5 5 5 是 2 2 2 关于模 9 9 9 的乘法逆元。所以 8 ÷ 2   m o d   9 = 8 × 5   m o d   9 = 4 8\div2\bmod9=8\times5\bmod9=4 8÷2mod9=8×5mod9=4。

有了乘法逆元之后， b ÷ a   m o d   p b\div a\bmod p b÷amodp，如果 a ， p a，p a，p 互质，那么就有：

b ÷ a   m o d   p = ( b   m o d   p × a − 1   m o d   p )   m o d   p b\div a\bmod p=(b\bmod p\times a^{-1}\bmod p)\bmod p b÷amodp=(bmodp×a−1modp)modp

费马小定理：若 p p p 是质数，对任意整数 a a a 不是 p p p 的倍数，有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod p ap−1≡1(modp)，也可以写作 a p ≡ a ( m o d p ) a^{p}\equiv a\pmod p ap≡a(modp)。

证明：根据同余的性质， a , 2 a , 3 a … … , ( p − 1 ) a a,2a,3a……,(p-1)a a,2a,3a……,(p−1)a 分别   m o d   p \bmod p modp 的结果各不相同。那么：

a × 2 a × 3 a … … × ( p − 1 ) a ≡ 1 × 2 × 3 … … × ( p − 1 ) ( m o d p ) a p − 1 × [ 1 × 2 × 3 … … × ( p − 1 ) ] ≡ 1 × 2 × 3 … … × ( p − 1 ) ( m o d p ) a p − 1 ≡ 1 ( m o d p ) \begin{aligned}a\times2a\times3a……\times(p-1)a&\equiv 1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}\times[1\times2\times 3……\times(p-1)]&\equiv1\times2\times 3……\times(p-1)\pmod p\\a^{p-1}&\equiv 1\pmod p\end{aligned} a×2a×3a……×(p−1)aap−1×[1×2×3……×(p−1)]ap−1​≡1×2×3……×(p−1)(modp)≡1×2×3……×(p−1)(modp)≡1(modp)​

如何求乘法逆元： 若 p p p 是质数，则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod p ap−1≡1(modp)，而 a × x ≡ 1 ( m o d p ) a\times x\equiv 1\pmod p a×x≡1(modp)，所以 a p − 2 a^{p-2} ap−2 是 a a a 模 p p p 意义下的的乘法逆元。

可以用快速幂，时间复杂度为 O ( log ⁡ p ) O(\log p) O(logp)。

a ( n − 1 ) ! ≡ a n ! × n ( m o d p ) [ ( n − 1 ) ! ] − 1 ≡ ( n ! ) − 1 × n ( m o d p ) \begin{aligned} a\over{(n-1)!}&{\equiv} {{a}\over{n!}}\times n{\pmod p}\\ [(n-1)!]^{-1}&\equiv (n!)^{-1}\times n\pmod p\end{aligned} (n−1)!a​[(n−1)!]−1​≡n!a​×n(modp)≡(n!)−1×n(modp)​

i n v [ n ] inv[n] inv[n] 表示 n n n 的阶乘在模 p p p 意义下的的乘法逆元 ( n < p ) (n1 i>1 时的逆。

设 k k k 是 p ÷ i p\div i p÷i 的商， r r r 是 p ÷ i p\div i p÷i 的余数，则 k × i + r ≡ 0 ( m o d p ) k\times i+r\equiv 0\pmod p k×i+r≡0(modp)；

在等式两边同乘 i − 1 × r − 1 i^{-1}\times r^{-1} i−1×r−1，得到 k × r − 1 + i − 1 ≡ 0 ( m o d p ) k\times r^{-1}+i^{-1}\equiv 0\pmod p k×r−1+i−1≡0(modp)；

移项得到 i − 1 ≡ − k × r − 1 ( m o d p ) i^{-1}\equiv -k\times r^{-1}\pmod p i−1≡−k×r−1(modp)，即 i − 1 ≡ − ⌊ p i ⌋ × r − 1 ( m o d p ) i^{-1}\equiv -\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p i−1≡−⌊ip​⌋×r−1(modp)；

最后右边加上 p p p ，得到 i − 1 ≡ p − ⌊ p i ⌋ × r − 1 ( m o d p ) i^{-1}\equiv p-\lfloor{{p}\over{i}} \rfloor\times r^{-1}\pmod p i−1≡p−⌊ip​⌋×r−1(modp)。

下面是洛谷 P3811 乘法逆元 的部分代码：