线性逆元推导记录

· · 个人记录

看完了数学一本通的线性逆元，再自行推导一下。
记 a 的逆元为 a^{-1}
已知：1^{-1} \equiv 1 \pmod p
设 k = \lfloor \frac{p}{i}\rfloor,r = p \bmod i,p = k \cdot i + r

k \cdot i + r \equiv 0 \pmod p (k \cdot i + r) \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p k \cdot i \cdot i^{-1} \cdot r^{-1} + r \cdot i^{-1} \cdot r^{-1} \equiv 0 \pmod p k \cdot r^{-1} + i^{-1} \equiv 0 \pmod p i^{-1} \equiv -k \cdot r^{-1} \pmod p i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p

总体推导思路：先将 p 用已知量表示出来，然后通过乘上一些数使得这个式子的其中一项为要求的逆元（i^{-1}），然后移项得到结果。