若整数a、b满足同余方程a∗b≡1(mod n) ，那么a，b互为模n意义下的逆元

逆元存在的充要条件为gcd（a，n）为1.

除法不可以使用之前分部的策略，否则结果将会产生问题。

1.若 ( a / b ) mod n = m，左右同时乘以 b 由于m 与（a/b）是关于模n同余的， 根据同余式的性质： 若a≡b (% p)，则对于任意的c，都有 (a * c) ≡ (b * c) (%p)

所以此时有： a % n = （m * b）% n 2.若存在x，可使得 a * x = m%n，将x与上式的左右相乘 根据相同的性质，得： （a * x）% n = （m * x * b）% n = m % n 也就意味着 （b * x）%n = 1; 即 x，b互为模n意义下的逆元

那么证得通过a 乘上 b 对模n的逆元可以求出(a/b) mod n

扩展欧几里得算法 a ∗ x ≡ 1 ( mod n) 可以化为：a* x = k * n + 1 a * x + （-k ）* n = 1 即 a * x + n * k = 1 满足扩展欧几里得的格式，若此时gcd （a，n）！=1，那么此时方程无解，即不存在逆元

若满足gcd （a，n）的条件，根据扩展欧几里得算法就可以直接求出一个x，当然此时的解也不唯一，不过我们一般都是使用exgcd所得的那个特解。 对exgcd所得的那个解进行处理，保证其为一个正整数。 x%mod+mod)%mod

费马小定理： 若p为素数，则有a^(p-1) ≡ 1(mod p)

欧拉定理（费马小定理的推广）： 若a、p互素，则有a^φ( p) ≡ 1(mod p)

两个定理的证明

在费马小定理中，a ^ (p-2)∗a ≡ 1(mod p) a ^ (p-2）就是a在mod p意义下的逆元;

在欧拉定理中，a^（φ( p)-1）* a ≡ 1(mod p) a^（φ( p)-1）就是a在mod p意义下的逆元

那么我们就转化为了求快速幂的问题。至于求欧拉函数的方法会在后面讲。

总之只要p为素数，就可以使用费马小定理直接快速幂求解； 若不为素数，就需要先求出p的欧拉函数再进行快速幂求解。

给定模 p 和 n，可以在线性时间内求出1 到 n 对 p 取模的逆元。

p为一个不算太大的质数

已知边界条件为 inv[ 1 ] = 1; 目标是求 i 模 p 的逆元 p 可以表示为 k * i + r； 其中存在关系： k = p / i； r = p % i；

根据 p = k * i + r 可以得到：（ k * i + r） ≡ 0 （mod p） 对左右同时乘以（r ^ -1）*(i ^ -1)， 可以得到：k∗（r ^ -1）+(i ^ -1)≡0 (mod p) 可以转化为：(i ^ -1)≡（−k∗（r ^ -1））(mod p) 即inv[ i ] = （-k * inv[ r ] ）（mod p）=（−p/i ∗ inv[p%i]）(mod p)

此时我们就可以用inv[p%i] 的结果来计算inv[ i ]的结果。