Acm数论Eular.doc_第1页
Acm数论Eular.doc_第2页
Acm数论Eular.doc_第3页
Acm数论Eular.doc_第4页
Acm数论Eular.doc_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

定理 一：设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r)。证明是用反证法，这里略去。Code:int Euclid(int a,int b)int r;while(b!=0)r=a%b;a=b;b=r;return a;进一步优化为:int gcd(int a,int b)return b?gcd(b,a%b):a;另外有:int lcm(int a,int b)return a/gcd(a,b)*b;定理 二：如果说 a|b且 a|c ,则对任意的整数 x,y,有a|xb+yc.这就是我们常用的gcd(b,c)=xb+yc依据。扩展的欧几里德算法: 设a和b不全为0，则存在整数x和y使得gcd(a,b)= ax+by;Code:int ExEuclid(int a,int b,int &x,int &y)if(b=0)x=1;y=0;return a;int r=ExGcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return r;证明：对于a=b,b=a%b.求x,y使得ax+by=Gcd(a,b); 由于 b=a%b=a-a/b*y; 则ax + by = Gcd(a,b) = bx + (a-a/b*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互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Eulers totient function、函数、欧拉商数等。 例如(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。函数的值 Euler函数通式：(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4).(1-1/pn),其中p1, p2pn为x的所有质因数，x是不为0的整数。(1)=1（唯一和1互质的数就是1本身）。 比如12=2*2*3 那么（12）=12*（1-1/2）*(1-1/3)=4) 下面是欧拉函数的性质：若n是质数p的k次幂，(n)=pk-p(k-1)=(p-1)p(k-1)，因为除了p的倍数外，其他数都跟n互质（即只有一个质数因子p）。(n)=pk(1-1/p)=pk(p-1)/p=p(k-1)(p-1).欧拉函数是积性函数若m,n互质，(mn)=(m)(n)。 特殊性质：当n为奇数时，(2n)=(n), 证明于上述类似。求1.n-1中与n互质的数的个数,即(n)=?Code:int
人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论