欧拉函数积性公式证明.doc

《欧拉函数积性公式证明.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、欧拉函数积性公式证明定义：两个整数相除N/m一定可以表示为N=m·u+r，在初等数论中称m为模，r为剩余，如果r为非负整数那么r∈{0,1,2,...，m-1}中一个。表示式可简化为N≡rmodm；模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

2、分别是模q和p互质的剩余集（记Zq和Zp）的元素，根据中国剩余定理，即联立不定方程N≡amodq，N≡bmodp的解→N≡rmodq·p，r是唯一的，r≡(ap·p-1+bq·q-1)modq·p，p-1是p的逆，p·p-1≡1modq。且对于不同的a或b，集合{(ap·p-1+bq·q-1)modq·p}的元素两两不相交，否则△a·pp-1≡△b·qq-1modq·p，由于△a＜q、△b＜p，故等式不成立。于是根据乘法原理对于不同的a或b集合Zq×Zp与Zqp一一对应，故φ(q·p)=φ(q)·φ(p)。定理2：pj(j=1,2,...)均为不同的素数，

3、欧拉函数可以表示为φ(m)=m·∏(1-1/pj)(j为m的素因子的个数)。证：根据算数基本定理任何整数可以表示为m=∏pjkj,以及φ(pk)=pk-pk-1(与pk有公约数的剩余个数)=(p-1)pk-1，两式结合就得到上述著名的欧拉函数公式。