引理:

缩系:

简单的定义:对于m(m>1),在[1,m]区间中所有与m互素的数可以构成一个缩系。
缩系性质1、缩系中必定每个元素都有自己唯一的逆元,并且每个元素的逆元不与其他元素的重复(一一对应的关系)。
缩系性质2、对于任意的与n互质的正整数k,若{A1,A2,...,Am}为模n的一个缩系,(k,n)=1,则{kA1,kA2,...,kAm}也为模n的一个缩系 .
缩系性质3、由缩系性质1导出:$\Pi A_i = 1$

逆元的定义:

在mod p意义下,若ab=1,那么ab互为对方的逆元。
定理一:在mod p(p为质数)意义下,任意一个数x(1<=x< p)都有它的逆元
证明:首先{1,2,...,p-1}是一个缩系。(显然)
由缩系性质1:定理1成立。
定理二:在mod q(q不是质数)意义下,如果(a,q)==1(a在mod q的缩系内),a有逆元。如果(a,q)!=1,那么a没有逆元
证明:(显然)
定理三:在mod p 意义下,如果ab=1,那么x/a=xb;
证明:因为ab=1,所以1/a=b,所以x(1/a)=xb

所以,如果p为质数,我们就可以放心地求p以内所有数的逆元。


逆元求法1:扩展欧几里德算法(ap互质)(lnn)

由于逆元的定义:xa=1(mod p)
所以我们可以用扩展欧几里德算法求出使ax=1的x,xa+yp=1

逆元求法2:费马定理(p为质数,xp互素)(logn)

费马定理:$x^{(p-1)}=1(mod p)$
证明:这里需要应用缩系的性质2、3。
令$$s=x^{(p-1)}(p-1)!$$
那么$$s=1x\times(2x)\times(3x)\times...\times((p-1)x)$$
由缩系性质2:这也是一个缩系的所有元素的积。因此$s=1$
因为(p-1)!是一个缩系的所有元素的积,所以(p-1)!=1
因此可以说明$x^{(p-1)}$也为1时s才为1。
证毕

逆元求法3:欧拉函数(ap互质)(sqrt(n))

欧拉定理:$a^{phi(p)} = 1 (mod p)$
证明:令S为mod p意义下缩系的元素之积,因此S=1
那么:$a^{phi(p)}S=1$
证毕

逆元求法4:线性递推(p为质数)(平均每个O(1))

首先证明$i^{-1}=(pmod i)^{-1}(p-[\frac{p}{i}])$
证明:
$$p mod i = p - [\frac{p}{i}]i$$
$$p mod i = -[\frac{p}{i}]i$$
由于$x/a=xa^{-1}$(其中a^{-1}为a的逆元),所以我们经过移项得:
$$i^{-1}=-[\frac{p}{i}](p mod i)^{-1}$$
也就是:
$$i^{-1}=(p-[\frac{p}{i}])(p mod i)^{-1}$$