我知道用小费马定理求乘法逆元，但是有的时候会忘记为什么要使用它
a p − 2 ⋅ a ≡ 1 ( m o d p ) , w h e n g c d ( a , p ) = 1 a^{p-2} \cdot a \equiv 1(mod\; p),\;when \;gcd(a,p) = 1 ap−2⋅a≡1(modp),whengcd(a,p)=1
- 求
A
/
B
m
o
d
p
A / B \mod p
A/Bmodp，万一 A 或者 B 太大了，无法算出怎么办？
- 想引入模运算对不对？除法法则不存在嘿嘿！
- 引入乘法逆元，改造式子 A ⋅ B − 1 m o d p A \cdot B^{-1} \mod p A⋅B−1modp
- 再应用乘法法则，引入模运算，使得中间结果维持在一个可表示的数据范围
- 还是求那个，但是我直接给 A m o d p A \mod p Amodp，这下 A 彻底算不了了，必须采用乘法法则，所以必须采用乘法逆元改除为乘