数学竞赛辅导讲座同余

数学竞赛辅导讲座同余

ID:42686529

大小:645.00 KB

页数:12页

时间:2019-09-20

数学竞赛辅导讲座同余_第1页
数学竞赛辅导讲座同余_第2页
数学竞赛辅导讲座同余_第3页
数学竞赛辅导讲座同余_第4页
数学竞赛辅导讲座同余_第5页
资源描述:

《数学竞赛辅导讲座同余》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数学竞赛辅导讲座:同余知识、方法、技能同余是数论中的重要概念,同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念,剩余类和完全剩余系,同余方程,整数模的阶和中国剩余定理.Ⅰ.基本概念定义一:设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同,则称a、b对模m同余,记为a≡b(modm);否则,记为a≡b(modm).例如,15≡7(mod4),-23≡12(mod7).同余有如下两种等价定义法:定义一*若m

2、a-b,则称a、b对模m同余.定义一**若a=b+mt(t∈Z),则称a、b对模m同余.同余

3、的基本性质:(1)(2)(3)若①②(4)若特别地,设,则(5)若特别地,又若(c,m)=1,则-12-【证明】因这等价于又因若(a,b)==1(d≠0)及b

4、ac,且(b,c)=1从而有这个性质说明同余式两边的同一非零因数,不能像等式那样“约去”,只有当这非零因数与模互质时,才可“约去”.(6)而(7)设①若c>0,则②d为a、b、m的任一公约数,则(8)若(9)若Ⅱ.剩余类和完全剩余系若按对某一模m的余数进行分类,就可以引入所谓的剩余类和完全剩余系的概念.定义二:设m∈N*,把全体整数按其对模m的余数r(0≤r≤m-

5、1)归于一类,记为kr,每一类kr(r=0,1,…,m-1)均称模m的剩余类(又叫同余类).同一类中任一数称为该类中另一数的剩余.剩余类kr是数集,它是一个公差为m的(双边无穷)等差数列.根据定义,剩余类具有如下性质:(1)(2)对任一数n∈Z,有惟一的;(3)对任意的a,b∈Z,a,b定义三:设是模m的(全部)剩余类.从每个kr中任取一个数ar,这m-12-个数组成的一个组称为模m的一个完全剩余系,简称完系.例如,取m=4,则有,k2={…,-6,-2,2,6,10,…},k3={…,-5,-1,3,7,11,…}.数

6、组0,1,2,3;-8,5,2,-1等等都是模的4的一个完全剩余系.显然,模m的完全剩余系有无穷多个.但最常用的是下面两种:(1)非负数最小完全剩余系:0,1,2,…,m-1;(2)绝对值最小完全剩余系:它随m的奇偶性不同而略有区别.当(对称式)当由定义不难得到如下判别完全剩余系的方法:定理一:m个整数是模m的一个完系≡定理二:设(b,m)=1,c为任意整数.若为一个完系,则也是模m的一个完全剩余系.特别地,任意m个连续整数构成模m的一个完全剩余系.【证明】只需证明:当而这可用反证法得证.下略.设m为一正整数,由于在0,

7、1,…,m-1中与m互质的数的个数是由m惟一确定的一个正整数,因此,可给出如下定义.定义四:m为一正整数,把0,1,…,m-1与m互质的数的个数叫做m的欧拉函数,记为显然,的定义域是正整数N*,前n个值为:当m=p为质数时,设k是模的一个剩余类.若a、b∈k,则于是由性质9知,(a,m)=(b,m).因此,若(a,m)=1,则k中的任一数均与m互质.这样,又可给出如下定义定义五:如果一个模m的剩余类kr中任一数与m互质,则称kr是与模m互质的剩余类;在与模m互质的每个剩余类中任取一个数(共个)所组成的数组,称为模m的一个

8、简化剩余系.-12-例如,取m=6,在模6的六个剩余类中,是与模6互质的剩余类.数组1,5;7,-7;1,-1;等等都是模6的简化剩余类.由此定义,不难得到:定理三:是模m的简化剩余系定理四:在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系.这两个定理,前者是简化剩余系的判别方法,后者是它的构造方法.显然,模m的简化剩余系有无穷多个,但常用的是“最小简化剩余系”,即由1,2,…,m-1中与m互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五:设是模m的简化剩余系.若(

9、k,m)=1,则也是模m的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略.定理六:(欧拉定理)若(a,m)=1,则特别地,(费马小定理)若m=p为质数,pa,则定理七:(威尔逊定理)设p素数,则(p-1)!定理八:(欧拉函数值计算公式)令m的标准分解式为,则例如,30=2·3·5,则读者应认识到:由于任何整数都属于模m的某一剩余类,所以,在研究某些整数性质时,选取适当的(模)m,然后在模m的每个剩余类中取一个“代表数”(即组成一个完全剩余系),当弄清了这些代表数的性质后,就可弄清对应的剩余类中所有数的性质,进而

10、弄清全体整数的性质,这就是引入剩余类和完全剩余系的目的.Ⅲ.同余方程设的整系数多项式.类似于多项式和代数方程式的有关定义,我们有-12-定义六:同余式叫做一元n次同余方程.例如,是七次同余方程.定义七:若c使得叫做同余方程的一个解.显然,同余方程的解是一些剩余类,而不仅是一个或n个类.例如,都是二次同余方程的解.1.

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。