首先：逆元定义

我们先说明一下什么是逆元
逆元是指，在模\(P\)的意义下，\(a\)和\(x\)的积模\(P\)后等于1
式子：\(a*x≡1\) \((mod\) \(P)\)

其次：费马小定理

有了逆元的定义后，我们引入一下费马小定理
何为费马小定理？指在\(P\)是质数的情况下，一定有\(a^{P-1}≡1\) \((mod\) \(P)\)
证明是没有证明的啦，要证明自己去搜啦

最终：费马小定理求逆元

现在我们手上有两个式子
一是逆元：\(a*x≡1\) \((mod\) \(P)\)
二是费马小定理：\(a^{P-1}≡1\) \((mod\) \(P)\)
诶，这两个式子是不是有点想
我们把费马小定理的式子转一下

此时再和逆元的式子对比一下
发现：似乎，\(x\)就是\(a^{P-2}\)
自信点，把似乎去掉
至此，我们就知道了，在P是质数时，\(a\)在模\(P\)的意义下的逆元就是\(a^{P-2}\)
大功告成
切记，只有模数\(P\)是质数的情况下才可以用费马小定理求逆元
顺便说一下，求\(a^{P-2}\)可以用快速幂

教学之费马小定理求逆元

原文：https://www.cnblogs.com/H-K-H/p/13448482.html