搜索
欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n)。完全余数集合：定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。显然|Zn|＝φ(n)。有关性质：对于素数p，φ(p)=p-1。对于两个不同素数p，q，它们的乘积n=p*q满足φ(n)=(p-1)*(q-1)。这是因为Zn={1,2,3,...,n-1}-{p,2p,...,(q-1)*p}-{q,2q,...,(p-1)*q}，则φ(n)=(n-1)-(q-1)-(p-1)=(p-1)*(q-1)＝φ(p)*φ(q)。欧拉定理：对于互质的正整数a和n，有aφ(n)≡1modn。证明：(1)令Zn={x1,x2,...,xφ(n)}，S={a*x1modn,a*x2modn,...,a*xφ(n)modn}，则Zn=S。①因为a与n互质，xi(1≤i≤φ(n))与n互质，所以a*xi与n互质，所以a*ximodn∈Zn。②若i≠j，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn（消去律）。(2)aφ(n)*x1*x2*...*xφ(n)modn≡(a*x1)*(a*x2)*...*(a*xφ(n))modn≡(a*x1modn)*(a*x2modn)*...*(a*xφ(n)modn)modn≡x1*x2*...*xφ(n)modn对比等式的左右两端，因为xi(1≤i≤φ(n))与n互质，所以aφ(n)≡1modn（消去律）。注：消去律：如果gcd(c,p)=1，则ac≡bcmodp⇒a≡bmodp。费马定理：若正整数a与素数p互质，则有ap-1≡1modp。证明这个定理非常简单，由于φ(p)=p-1，代入欧拉定理即可证明。*****************************************************************************补充：欧拉函数公式(1)pk的欧拉函数对于给定的一个素数p，φ(p)=p-1。则对于正整数n=pk，φ(n)=pk-pk-1证明：小于pk的正整数个数为pk-1个，其中和pk不互质的正整数有{p*1,p*2,...,p*(pk-1-1)}共计pk-1-1个所以φ(n)=pk-1-(pk-1-1)=pk-pk-1。(2)p*q的欧拉函数假设p,q是两个互质的正整数，则p*q的欧拉函数为φ(p*q)=φ(p)*φ(q)，gcd(p,q)=1。证明：令n=p*q，gcd(p,q)=1根据中国余数定理，有Zn和Zp×Zq之间存在一一映射（我的想法是：a∈Zp，b∈Zq⇔b*p+a*q∈Zn。）所以n的完全余数集合的元素个数等于集合Zp×Zq的元素个数。而后者的元素个数为φ(p)*φ(q)，所以有φ(p*q)=φ(p)*φ(q)。(3)任意正整数的欧拉函数任意一个整数n都可以表示为其素因子的乘积为：In=∏piki(I为n的素因子的个数)i=1根据前面两个结论，很容易得出它的欧拉函数为：IIΦ(n)=∏piki-1(pi-1)=n∏(1-1/pi)i=1i=1对于任意n2，2|Φ(n),因为必存在pi-1是偶数。//直接求解欧拉函数inteuler(intn){//返回euler(n)intres=n,a=n;for(inti=2;i*i=a;i++){if(a%i==0){res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出while(a%i==0)a/=i;}}if(a1)res=res/a*(a-1);returnres;}//筛选法打欧拉函数表#defineMax1000001inteuler[Max];voidInit(){euler[1]=1;for(inti=2;iMax;i++)euler[i]=i;for(inti=2;iMax;i++)if(euler[i]==i)for(intj=i;jMax;j+=i)euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出}