模运算中的逆元

有些题目的结果非常大，所以经常会把结果模一个大数。模运算在加减乘幂时性质都保持，如下图：

但除法例外，即：

那如何解决这个问题呢？把除法变成乘法，这就涉及到逆元的概念。
1、什么是逆元？ac1(mod p)，则c叫做a的逆元，记作a^-1，则(mod p) = ab^-1(mod p)，这样模的除法就变成了乘法。
2、如何求逆元？
方法1：若p为质数，根据费马小定理，a^p-11 (mod p)，两边同乘a^-1，则a^-1a^p-2(mod p)，即a^-1=a^p-2(mod p)，而a^p-2可以用快速幂求。

方法2：扩展欧拉算法。

参考：
1、数论篇4——逆元（数论倒数）