乘法逆元

那么存在一个b，使得假设$gcd(a,p) = 1$,则有$a*b ≡ 1 (mod p) $ 即 $ab=pk+1$

b就叫做a关于模p的乘法逆元

费马小定理：当a,p满足$gcd(a,p) = 1$ 则有$a^p≡a(modp)$

变一下形：$a⋅a ^{p-2}≡1(mod\ p)$。是不是和上面的乘法逆元的定义是相似的？

所以，我们可以使用快速幂求出$a^{p - 2}$，即求出a的逆元

扩展欧几里得：找出整数对（x，y），使得$ax+by = gcd(a,b)$

$ab=pk+1$ 移项得到 $ab-pk=1$

b就对应x，-k对应y

空。没看懂

1.存在唯一性

2.完全积性函数

把 a 的逆元表示为 inv[a]

两个数的逆元的积等于这两个数积的逆元， inv[a] * inv[b]=inv[a * b]

3.费马小定理得$a^{p-2} = 1/a(mod\ p)$

$b/a = b * a^{p-2}$ 即 b * inv[a] = b / a (mod p)