QB_UDG 2016年11月8日10:16:18
如果 p是素数，且a与p互质，即gcd(a,p)=1 那么(a^p-1) ≡ 1 (mod p)
应用： 求乘法逆元
乘法逆元: (x*x’)≡ 1 (mod p) 称x’为x模p的乘法逆元 (注意，一定要是余1)
逆元 ：(b/a) (mod n) = (b * x) (mod n)。 x表示a的逆元。并且 a*x ≡ 1 (mod n) 注意：只有当a与n互质的时候才存在逆元
注意，逆元也可以这样理解，求一个最小的正整数x（逆元），使a乘以x对m的取余等于1对m的取余， 所以m=1 时，逆元为1
因为(a^p-1) ≡ 1 (mod p) 那么 (a*a^p-2)≡ 1 (mod p) 所以 a^p-2就是a关于模p的乘法逆元
逆元用处：
在求解除法取模问题(a/b)%m时，我们可以转化为(a%(b∗m))/b， 但是如果b很大，则会出现爆精度问题，所以我们避免使用除法直接计算。 可以使用逆元将除法转换为乘法： 假设b存在乘法逆元，即与m互质（充要条件）。设c是b的逆元，即b∗c≡1(mod m)，那么有a/b=(a/b)∗1<=>(a/b)∗b∗cóa∗c (mod m) 即，除以一个数取模等于乘以这个数的逆元取模。
于是求(a/b)mod p 就转换为求(a*b’)mod p =( (a mod p)*(b^p-2 mod p) )mod p
适用于P为质数
通式1：φ(x)=x*(1- 1/p1)(1- 1/p2)(1- 1/p3)…..(1- 1/pn) 其中p1, p2，p3……pn为x的所有质因数
通式2：若x是质数p的k次幂,即x=p^k,有φ(x) = p^k - p^(k-1) = (p-1)*p^(k-1) 因为x的质因数只有p,所以除了p的倍数外，其他数都跟x互质。（程序中我们一般将φ(x)写成phi(x)）。
性质：
1.若x,y互质(即gcd(x,y)=1),那么φ(x*y)=φ(x)*φ(y) 2.若x是奇数φ(2x)=φ(x) 3.若x是质数φ(x)=x-1 4.若x>2,φ(x)为偶数
以上四条均可以根据欧拉函数推出！且显然！
若a,n为正整数，且a,n互质(即gcd(a,n)=1)，则有：
a^φ(n)≡ 1 (mod n)
根据此定理，费马小定理即为显然，因为质数p的phi(p)就等于p-1
应用：
a与n互质，当b很大时,可用欧拉定理降幂
(a^b) mod n = (a^(b mod phi(n))) mod n
最后提一下，怎么求phi(p)呢？
详见欧拉筛：
需要用到如下性质( p为质数 )： phi(p)=p-1 因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质
如果i mod p = 0, 那么 phi(i * p)=p * phi(i) 若整数n 不与i互质，n+i依然与i不互质 若整数n与i互质，n+i与i依然互质,证明:
若i mod p ≠0, 那么 phi( i * p )=phi(i) * ( p-1 ) i mod p 不为0且p为质数, 所以i与p互质, 那么根据欧拉函数的积性 phi(i * p)=phi(i) * phi(p) 其中phi(p)=p-1即第一条性质
#include<iostream> #include<cstdio> #define N 40000 using namespace std; int n; int phi[N+10],prime[N+10],tot,ans; bool mark[N+10]; void getphi() { int i,j; phi[1]=1; for(i=2;i<=N;i++)//相当于分解质因式的逆过程 { if(!mark[i]) { prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。 phi[i]=i-1;//当 i 是素数时 phi[i]=i-1 } for(j=1;j<=tot;j++) { if(i*prime[j]>N) break; mark[i*prime[j]]=1;//确定i*prime[j]不是素数 if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数 { phi[i*prime[j]]=phi[i]*prime[j];break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性 } } } int main() { getphi(); }
总结一下： 说白了，除以一个数取模的话，和乘以这个数的逆元取模效果是一样的。 求逆元其实就是求使A*X = 1 (mod C)成立的X，其中A是除法中的除数(貌似又要扯到扩欧、、)
求解除法取模问题(a/b)%m，我们可以转成(a*b’)mod m来解决，其中b’是b的逆元
降幂、 a与n互质，当b很大时,可用欧拉定理降幂
(a^b) mod n = (a^(b mod phi(n))) mod n
