歐拉函數(shù)公式及其證明

《歐拉函數(shù)公式及其證明》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、歐拉函數(shù)：歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù)，歐拉函數(shù)是指：對(duì)于一個(gè)正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)（包括1）的個(gè)數(shù)，記作φ(n)。完全余數(shù)集合：定義小于n且和n互質(zhì)的數(shù)構(gòu)成的集合為Zn，稱(chēng)呼這個(gè)集合為n的完全余數(shù)集合。顯然

2、Zn

3、＝φ(n)。有關(guān)性質(zhì)：對(duì)于素?cái)?shù)p，φ(p)=p-1。對(duì)于兩個(gè)不同素?cái)?shù)p，q，它們的乘積n=p*q滿(mǎn)足φ(n)=(p-1)*(q-1)。這是因?yàn)閆n={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

4、-1)＝φ(p)*φ(q)。歐拉定理：對(duì)于互質(zhì)的正整數(shù)a和n，有aφ(n)≡1modn。證明：(1)令Zn={x1,x2,...,xφ(n)}，S={a*x1modn,a*x2modn,...,a*xφ(n)modn}，則Zn=S。①因?yàn)閍與n互質(zhì)，xi(1≤i≤φ(n))與n互質(zhì)，所以a*xi與n互質(zhì)，所以a*ximodn∈Zn。②若i≠j，那么xi≠xj，且由a,n互質(zhì)可得a*ximodn≠a*xjmodn（消去律）。(2)aφ(n)*x1*x2*...*xφ(n)modn≡(a*x1)*(a*x2)*...*(a*xφ(n))modn≡(a

5、*x1modn)*(a*x2modn)*...*(a*xφ(n)modn)modn≡x1*x2*...*xφ(n)modn對(duì)比等式的左右兩端，因?yàn)閤i(1≤i≤φ(n))與n互質(zhì)，所以aφ(n)≡1modn（消去律）。注：消去律：如果gcd(c,p)=1，則ac≡bcmodp?a≡bmodp。費(fèi)馬定理：若正整數(shù)a與素?cái)?shù)p互質(zhì)，則有ap-1≡1modp。證明這個(gè)定理非常簡(jiǎn)單，由于φ(p)=p-1，代入歐拉定理即可證明。******************************************************************

6、***********補(bǔ)充：歐拉函數(shù)公式(1)pk的歐拉函數(shù)對(duì)于給定的一個(gè)素?cái)?shù)p，φ(p)=p-1。則對(duì)于正整數(shù)n=pk，φ(n)=pk-pk-1證明：小于pk的正整數(shù)個(gè)數(shù)為pk-1個(gè)，其中和pk不互質(zhì)的正整數(shù)有{p*1,p*2,...,p*(pk-1-1)}共計(jì)pk-1-1個(gè)所以φ(n)=pk-1-(pk-1-1)=pk-pk-1。(2)p*q的歐拉函數(shù)假設(shè)p,q是兩個(gè)互質(zhì)的正整數(shù)，則p*q的歐拉函數(shù)為φ(p*q)=φ(p)*φ(q)，gcd(p,q)=1。證明：令n=p*q，gcd(p,q)=1根據(jù)中國(guó)余數(shù)定理，有Zn和Zp×Zq之間存在一一

7、映射（我的想法是：a∈Zp，b∈Zq?b*p+a*q∈Zn。）所以n的完全余數(shù)集合的元素個(gè)數(shù)等于集合Zp×Zq的元素個(gè)數(shù)。而后者的元素個(gè)數(shù)為φ(p)*φ(q)，所以有φ(p*q)=φ(p)*φ(q)。(3)任意正整數(shù)的歐拉函數(shù)任意一個(gè)整數(shù)n都可以表示為其素因子的乘積為：In=∏piki(I為n的素因子的個(gè)數(shù))i=1根據(jù)前面兩個(gè)結(jié)論，很容易得出它的歐拉函數(shù)為：IIΦ(n)=∏piki-1(pi-1)=n∏(1-1/pi)i=1i=1對(duì)于任意n>2，2

8、Φ(n),因?yàn)楸卮嬖趐i-1是偶數(shù)。//直接求解歐拉函數(shù)inteuler(intn){//返回eu

9、ler(n)intres=n,a=n;for(inti=2;i*i<=a;i++){if(a%i==0){res=res/i*(i-1);//先進(jìn)行除法是為了防止中間數(shù)據(jù)的溢出while(a%i==0)a/=i;}}if(a>1)res=res/a*(a-1);returnres;}//篩選法打歐拉函數(shù)表#defineMax1000001inteuler[Max];voidInit(){euler[1]=1;for(inti=2;i

10、r(intj=i;j