Acm数论Eular

《Acm数论Eular》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、定理一：设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r)。证明是用反证法，这里略去。Code:intEuclid(inta,intb){intr;while(b!=0){r=a%b;a=b;b=r;}returna;}进一步优化为:intgcd(inta,intb){returnb?gcd(b,a%b):a;}另外有:intlcm(inta,intb){returna/gcd(a,b)*b;}定理二：如果说a

2、b且a

3、c,则对任意的整数x,y,有a

4、xb+yc.这就是我们常用的gcd(b,c

5、)=xb+yc依据。扩展的欧几里德算法:设a和b不全为0，则存在整数x和y使得gcd(a,b)=ax+by;Code:intExEuclid(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=ExGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}证明：对于a'=b,b'=a%b.求x,y使得a'x+b'y=Gcd(a',b');由于b'=a%b=a-a/b*y;则a'x+b'y=Gcd(a',b')===>bx+(a-a/b*

6、b)y=Gcd(a',b')=Gcd(a,b)===>ay+b(x-a/b*y)=Gcd(a,b);故，要求的x',y'分别是y和(x-a/b*y);下面说一下欧拉函数：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler'stotientfunction、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。φ函数的值Euler函数通式：φ(x)=x(1-1/p1)(1-1/

7、p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1,p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。比如12=2*2*3　　那么φ（12）=12*（1-1/2）*(1-1/3)=4)下面是欧拉函数的性质：若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质（即只有一个质数因子p）。φ(n)=p^k(1-1/p)=p^k(p-1)/p=p^(k-1)(p-1).欧拉函数是积性函数——若m,n互质，

8、φ(mn)=φ(m)φ(n)。特殊性质：当n为奇数时，φ(2n)=φ(n),证明于上述类似。求1...n-1中与n互质的数的个数,即φ(n)=?Code:intEular(intn){intret=1,i;for(i=2;i*i<=n;++i){if(n%i==0){n/=i;ret=ret*(i-1);while(n%i==0){n/=i;ret=ret*i;}}}if(n>1)ret*=(n-1);returnret;}