欧拉函数积性公式证明

欧拉函数积性公式证明欧拉函数积性公式证明定义:两个整数相除N/m一定可以表示为N=m?u+r，在初等数论中称m为模，r为剩余，如果r为非负整数那么r?{0,1,2,...，m-1}中一个。表示式可简化为N?r modm;模m对应的剩余集记rmodm。欧拉发现剩余集中的元素其中与模m互质的个数非常有意义，并从“若m与N互质，则r与m也互质”启发，找到了计算方法。为了纪念他以他的名字称谓欧拉函数φ(m)。如8的剩余集为{0,1,2，...，7}八个元素，但与8互质的为{1,3,5,7}只有4个，即φ(8)=4。定理1:若q与p...

欧拉函数积性公式证明定义:两个整数相除N/m一定可以表示为N=m?u+r，在初等数论中称m为模，r为剩余，如果r为非负整数那么r?{0,1,2,...，m-1}中一个。表示式可简化为N?r modm;模m对应的剩余集记rmodm。欧拉发现剩余集中的元素其中与模m互质的个数非常有意义，并从“若m与N互质，则r与m也互质”启发，找到了计算方法。为了纪念他以他的名字称谓欧拉函数φ(m)。如8的剩余集为{0,1,2，...，7}八个元素，但与8互质的为{1,3,5,7}只有4个，即φ(8)=4。定理1:若q与p互质，则φ(q?p)= φ(q)?φ(p)。证明:设a,b分别是模q和p互质的剩余集(记Zq和Zp)的元素，根据中国剩余定理，即联立不定方程N?a modq，N?b modp -1-1的解?N?r modq?p，r是唯一的，r?(ap?p+bq?q) modq?p， -1-1p是p的逆，p?p?1modq。且对于不同的a或b，集合 -1-1-1{(ap?p+bq?q) modq?p}的元素两两不相交，否则?a?p p -1??b?qq modq?p，由于?a,q、?b,p，故等式不成立。于是根据乘法原理对于不同的a或b 集合Zq×Zp与Zqp一一对应，故φ(q?p)=φ(q)?φ(p)。定理2:p (j=1,2,...)均为不同的素数，欧拉函数可以表示为 j φ(m)=m??(1-1/p) (j 为 m 的素因子的个数)。 j kj证:根据算数基本定理任何整数可以表示为m= ?p ,以及 j kkk-1kk-1φ(p)=p- p(与p有公约数的剩余个数)=(p-1)p，两式结合就得到上述著名的欧拉函数公式。

                    本文档为【欧拉函数积性公式证明】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

is_003124

暂无简介~

格式：doc

大小：11KB

软件：Word

页数：1

分类：生活休闲

上传时间：2017-09-27

浏览量：82

热点搜索

《静女》翻译、理解性默写、选择题及答案【统编版必修上册】(1) 北京师范大学老年大学招生简章上海工艺美术职业学院学分制管理规定(试行) SD高达G世纪F雇佣兵资料制度汇编-格式适合公司年会的歌曲包装材料进出台账【精品】国培计划（2012）四川省农村中小学骨干教师23 公交术语及解释(全) 软件工程课程设计报告_基于web在线作业提交批改系统圣经无误宣言除数是整数的小数除法职场广告制作费用申请 c语言图形题经典习题《静女》翻译、理解性默写、选择题及答案【统编版必修上册】(1) 北京师范大学老年大学招生简章上海工艺美术职业学院学分制管理规定(试行) SD高达G世纪F雇佣兵资料制度汇编-格式适合公司年会的歌曲包装材料进出台账【精品】国培计划（2012）四川省农村中小学骨干教师23 公交术语及解释(全) 软件工程课程设计报告_基于web在线作业提交批改系统圣经无误宣言除数是整数的小数除法职场广告制作费用申请 c语言图形题经典习题