欧拉函数公式及其证明.pdf

欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数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={x,x,...,x}，S={a*xmodn,a*xmodn,...,a*12φ(n)12xmodn}，φ(n)则Zn=S。①因为a与n互质，x(1≤i≤φ(n))与n互质，所以a*x与n互质，所以aii*xmodn∈Zn。i②若i≠j，那么x≠x，且由a,n互质可得a*xmodn≠a*xmodn（消ijij去律）。(2)aφ(n)*x*x*...*xmodn12φ(n)≡(a*x)*(a*x)*...*(a*x)modn12φ(n)≡(a*xmodn)*(a*xmodn)*...*(a*xmodn)modn12φ(n)≡x*x*...*xmodn12φ(n)对比等式的左右两端，因为x(1≤i≤φ(n))与n互质，所以aφ(n)≡i1modn（消去律）。注：消去律：如果gcd(c,p)=1，则ac≡bcmodpa≡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∈Zqb*p+a*q∈Zn。）所以n的完全余数集合的元素个数等于集合Zp×Zq的元素个数。而后者的元素个数为φ(p)*φ(q)，所以有φ(p*q)=φ(p)*φ(q)。(3)任意正整数的欧拉函数任意一个整数n都可以表示为其素因子的乘积为：In=∏pk(I为n的素因子的个数)iii=1根据前面两个结论，很容易得出它的欧拉函数为：IIΦ(n)=∏pk-1(p-1)=n∏(1-1/pi)iiii=1i=1对于任意n>2，2|Φ(n),因为必存在p-1是偶数。i//直接求解欧拉函数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(a>1)res=res/a*(a-1);returnres;}//筛选法打欧拉函数表#defineMax1000001inteuler[Max];voidInit(){euler[1]=1;for(inti=2;i<Max;i++)euler[i]=i;for(inti=2;i<Max;i++)if(euler[i]==i)for(intj=i;j<Max;j+=i)euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出}