- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
高中数学奥赛辅导第三讲同余
数学奥赛辅导 第三讲 同余
知识、方法、技能
同余是数论中的重要概念,同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念,剩余类和完全剩余系,同余方程,整数模的阶和中国剩余定理.
Ⅰ.基本概念
定义一:设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同,则称a、b对模m同余,记为a≡b(modm);否则,记为a≡b(modm).
例如,15≡7(mod4),-23≡12(mod7).
同余有如下两种等价定义法:
定义一* 若m|a-b,则称a、b对模m同余.
定义一**若a=b+mt(t∈Z),则称a、b对模m同余.
同余的基本性质:
(1)
(2)
(3)若
①
②
(4)若特别地,设,则
(5)若特别地,又若(c,m)=1,则
【证明】因这等价于又因若(a,b)==1(d≠0)及b|ac,且(b,c)=1
从而有
这个性质说明同余式两边的同一非零因数,不能像等式那样“约去”,只有当这非零因数与模互质时,才可“约去”.
(6)而
(7)设
①若c0,则
②d为a、b、m的任一公约数,则
(8)若
(9)若
Ⅱ.剩余类和完全剩余系
若按对某一模m的余数进行分类,就可以引入所谓的剩余类和完全剩余系的概念.
定义二:设m∈N*,把全体整数按其对模m的余数r(0≤r≤m-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个数组成的一个组称为模m的一个完全剩余系,简称完系.
例如,取m=4,则有,k2={…,-6,-2,2,6,10,…},k3={…,-5,-1,3,7,11,…}.数组0,1,2,3;-8,5,2,-1等等都是模的4的一个完全剩余系.
显然,模m的完全剩余系有无穷多个.但最常用的是下面两种:
(1)非负数最小完全剩余系:0,1,2,…,m-1;
m的奇偶性不同而略有区别.
当(对称式)
当
由定义不难得到如下判别完全剩余系的方法:
定理一:m个整数是模m的一个完系≡
定理二:设(b,m)=1,c为任意整数.若为一个完系,则也是模m的一个完全剩余系.
特别地,任意m个连续整数构成模m的一个完全剩余系.
【证明】只需证明:当而这可用反证法得证.下略.
设m为一正整数,由于在0,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的一个简化剩余系.
例如,取m=6,在模6的六个剩余类中,
是与模6互质的剩余类.数组1,5;7,-7;1,-1;等等都是模6的简化剩余类.
由此定义,不难得到:
定理三:是模m的简化剩余系
定理四:在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系.
这两个定理,前者是简化剩余系的判别方法,后者是它的构造方法.显然,模m的简化剩余系有无穷多个,但常用的是“最小简化剩余系”,即由1,2,…,m-1中与m互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.
定理五:设是模m的简化剩余系.若(k,m)=1,则也是模m的简化剩余系.
下面介绍两个有关欧拉函数的重要结论.其证明略.
定理六:(欧拉定理)若(a,m)=1,则
特别地,(费马小定理)若m=p为质数,p a,则
定理七:(威尔逊定理)设p素数,则(p-1)!
定理八:(欧拉函数值计算公式)令m的标准分解式为
,
则
例如,30=2·3·5,则
读者应认识到:由于任何整数都属于模m的某一剩余类,所以,在研究某些整数性质时,选取适当的(模)m,然后在模m的每个剩余类中取一个“代表数”(即组成一个完全剩余系),当弄清了这些代表数的性质后,就可弄清对应的剩余类中所有数的性质,进而弄清全体整数的性质,这就是引入剩余类和完全剩余系的目的.
Ⅲ.同余方程
设的整系数多项式.类似于多项式和代数方程式的有关定义,我们有
定义六:同余式叫做一元n次同余方程.例如,
是七次同余方程
文档评论(0)