《剩余系和欧拉函数》课件1

《《剩余系和欧拉函数》课件1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4剩余系和欧拉函数人教B版数学选修4-6《初等数论初步》定义1对于正整数m，则m个整数0,1,…,m-1中与m互素的整数个数记做(m),也就是Euler函数例如，容易验证(2)=1，(4)=2，(7)=6定义2设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。定义3对于正整数m，从模m的每个简化剩余类中各取一个数xi，构成一个集合{x1,x2,,x(m)}，称为模m的一个简化剩余系模m的一个简化剩余系的元素个数是(m)例1设m是一个正整数,则①0,1,…,m-1中与

2、m互素的整数全体组成模m的一个简化剩余系叫做模m的最小非负简化剩余系②1,…,m-1,m中与m互素的整数全体组成模m的一个简化剩余系叫做模m的最小正简化剩余系③-m+1,…,-1,0中与m互素的整数全体组成模m的一个简化剩余系叫做模m的最大非正简化剩余系④-m,-m+1,…,1中与m互素的整数全体组成模m的一个简化剩余系叫做模m的最大负简化剩余系⑤当m分别为偶数时,-m/2,-(m-2)/2,…,-1,0,1,…,(m-2)/2或-(m-2)/2,…,-1,0,1,…,(m-2)/2,m/2中与m互素的整数全体组成模m

3、的一个简化剩余系当m是奇数时,-(m-1)/2,…,-1,0,1,…,(m-1)/2中与是m互素的整数全体组成模m的一个简化剩余系上述两个简化剩余系统称为模m的一个绝对值最小简化剩余系定理1若a1,a2,…,a(m)是(m)个与m互素的整数,并且两两对模m不同余,则a1,a2,…,a(m)是模m的一简化剩余系定理2若(a,m)=1,rl,r2,…,r(m)是模m的一简化剩余系,则arl,ar2,…,ar(m)也是模m的一简化剩余系证明由定理1只需证明arl,ar2,…,ar(m)是模m两两互不同余,且都与m

4、互素即可.先证两两互不相同:假设ariarj(modm),其中1≤i,j≤(m).由于(a,m)=1,有rirj(modm),这与rl,r2,…,r(m)是模m的一简化剩余系矛盾,故ari≠arj(modm),即:arl,ar2,…,ar(m)中模m两两互不同余再证(a,m)=1,(r,m)=1,(ar,m)=1例2已知1,7,11,13,17,19,23,29是模30的简化剩余系(7,30)=1,构造一个简化剩余系定理3设m是一个正整数,(a,m)=1,则存在a’,使得aa’≡1(modm)证明,因为,(a

5、,m)=1故存在唯一的整数s,t满足sa+tm=1sa≡1(modm),取s=a’成立这里a’也叫做a模m的乘法逆元定理4设m1,m2N，(m1,m2)=1，又设分别是模m1与m2的简化剩余系，则A={m1ym2x；xX，yY}是模m1m2的简化剩余系。定理5设m,nN，(m,n)=1，则(mn)=(m)(n)证,由定理4直接得到定理6设n的标准分解式是n=是它的全部素因数，则(n)=证明:由定理5有(n)=对任意的素数p，(p)等于数列1,2,,p中与p（也就是与p）互素的整数的个数，

6、因此(p)=p(1)又n=,和(1)式结合起来就得到结论推论设pq是不同的素数,则(pq)=(p)(q)=(p-1)(q-1)下面进一步考察欧拉函数的性质定理7设n是一个正整数则证明:设C={1,…,n},按照与n的最大公因素分类,对d

7、n记Cd={m

8、1≤m≤n,(m,n)=d},因为,(m,n)=diff,(m/d,n/d)=1,所以Cd中的元素m的形式Cd={m=dk

9、1≤k≤n/d,(k,n/d)=1},故Cd的元素个数为(n/d),因为每个整数属于且仅属于一个类Cd因此,#C=,即,又当d遍历

10、n的正因素时,n/d也遍历n的所有正因素例3设整数n=50,利用定理8对其进行分类解,因为n的因素为1,2,5,10,15,25,50则C1={1,3,7,9,11,13,17,19,23,27,29,31,33,37,39,41,43,47,49}C2={2,4,6,8,12,14,16,18,22,24,26,28,32,34,36,3842,44,46,48}……..TheEnd