全部分类
搜索资料
    首页
    合同协议
    建设工程
    高中数学竞赛数论

    高中数学竞赛数论

    举报
    开通vip

    高中数学竞赛数论.PAGE.高中数学竞赛数论剩余类与剩余系1.剩余类的定义与性质定义1设m为正整数,把全体整数按对模m的余数分成m类,相应m个集合记为：K0,K1,…,Km-1,其中Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类。K0,K1,…,Km-1为模m的全部剩余类.性质且Ki∩Kj=φ.每一整数仅在K0,K1,…,Km-1一个里.对任意a、b∈Z,则a、b∈Kra≡b.2.剩余系的定义与性质定义2设K0,K1,…,Km-1为模m的全部剩余类,从每个Kr里任取一个ar,得m个数a0,a1,…,am-...

    高中数学竞赛数论
    .PAGE.高中 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 竞赛数论剩余类与剩余系1.剩余类的定义与性质<1>定义1设m为正整数,把全体整数按对模m的余数分成m类,相应m个集合记为：K0,K1,…,Km-1,其中Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类<也叫同余类>。K0,K1,…,Km-1为模m的全部剩余类.<2>性质<ⅰ>且Ki∩Kj=φ.<ⅱ>每一整数仅在K0,K1,…,Km-1一个里.<ⅲ>对任意a、b∈Z,则a、b∈Kra≡b.2.剩余系的定义与性质<1>定义2设K0,K1,…,Km-1为模m的全部剩余类,从每个Kr里任取一个ar,得m个数a0,a1,…,am-1组成的数组,叫做模m的一个完全剩余系,简称完系.特别地,0,1,2,…,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对最小完全剩余系:当m为奇数时,;当m为偶数时,或.<2>性质<ⅰ>m个整数构成模m的一完全剩余系两两对模m不同余.<ⅱ>若=1,则x与ax+b同时遍历模m的完全剩余系.证明:即证a0,a1,…,am-1与aa0+b,aa1+b,…,aam-1+b同为模m的完全剩余系,因a0,a1,…,am-1为模m的完系时,若aai+b≡aaj+b,则ai≡aj,矛盾!反之,当aa0+b,aa1+b,…,aam-1+b为模m的完系时,若ai≡aj,则有aai+b≡aaj+b,也矛盾!<ⅲ>设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//,其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因=1,所以,m2x/≡m2x//,m1y/≡m1y//,从而x/≡x//,y/≡y//,矛盾!3.既约剩余系的定义与性质<1>定义3如果剩余类Kr里的每一个数都与m互质,则Kr叫与m互质的剩余类.在与模m互质的全部剩余类中,从每一类中任取一个数所做成的数组,叫做模m的一个既约<简化>剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.<2>性质<ⅰ>Kr与模m互质Kr中有一个数与m互质；证明:设a∈Kr,=1,则对任意b∈Kr,因a≡b≡r,所以,===1,即Kr与模m互质.<ⅱ>与模m互质的剩余类的个数等于,即模m的一个既约剩余系由个整数组成<为欧拉函数>;<ⅲ>若=1,则x与ax同时遍历模m的既约剩余系.证明:因=1,=1,所以,=1.若ax1≡ax2,则有x1≡x2,矛盾!<ⅳ>若a1,a2,…,aφ是个与m互质的整数,并且两两对模m不同余,则a1,a2,…,aφ是模m的一个既约剩余系.证明:因a1,a2,…,aφ是个与m互质的整数,并且两两对模m不同余,所以,a1,a2,…,aφ属于个剩余类,且每个剩余类都与m互质,故a1,a2,…,aφ是模m的一个既约剩余系.<ⅴ>设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y分别历遍模m1,m2的完系时,m2x+m1y历遍模m1m2的完系.由==1,=1得==1,所以,=1,=1,故=1.反之若=1,则==1,所以,==1,因=1,所以,==1.证毕.推论1若m1,m2是两个互质的正整数,则.证明:因当x,y分别历遍模m1,m2的既约剩余系时,m2x+m1y也历遍模m1m2的既约剩余系,即m2x+m1y取遍个整数,又x取遍个整数,y取遍个整数,所以,m2x+m1y取遍个整数,故.推论2设整数n的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式为<为互异素数,>,则有.证明:由推论1得,而,<即从1到这个数中,减去能被整除的数的个数>,所以,.4.欧拉与费尔马定理欧拉定理设m是大于1的整数,=1,则.证明:设r1,r2,…,r是模m的既约剩余系,则由性质3知ar1,ar2,…,ar也是模m的既约剩余系,所以,ar1ar2…ar≡r1r2…r,即,因<,m>=1,所以,.推论设p为素数,则对任意整数a都有.证明:若=1,由及Euler定理得即;若≠1,则p|a,显然有.例1设m>0,证明必有一个仅由0或1构成的自然数a是m的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm的同一剩余类中,它们的差即为所求的a.例2证明从任意m个整数a1,a2,…,am中,必可选出若干个数,它们的和<包括只一个加数>能被m整除.证明:考虑m个数a1,a1+a2,a1+a2+a3,…,a1+a2+…+am,如果其中有一个数能被m整除,则结论成立,否则,必有两个数属于modm的同一剩余类,这两个数的差即满足要求.例3设f=5x+2=f1,fn+1=f[fn].求证:对任意正整数n,存在正整数m,使得2011|fn.证明:因f2=f[f]=5<5x+2>+2=52x+5×2+2,f3=f[f2]=53x+52×2+5×2+2,…,fn=5nx+5n-1×2+5n-2×2+…+2,因<5n,2011>=1,所以,x与fn同时历遍mod2011的完系,1≤x≤2011,所以,存在正整数m<1≤m≤2011>使得fn≡0,即2011|fn.例4设是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数,数被除的余数都各不相同.证明:在数列中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a1=0.此时对每个正整数k必有∣ak∣,矛盾.现在对k归纳证明a1,a2,…,ak适当重排后是绝对值小于k的k个相邻整数.k=1显然.设a1,a2,…,ak适当重排后为-,…,0,…,i<0≤i≤k-1>,由于a1,a2,…,ak,ak+1是的一个完全剩余系,故必ak+1≡i+1,但∣ak+1∣,从而a1,a2,…,ak,ak+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1>.任一整数在数列中最多出现一次;2>.若整数u和v都出现在数列中,则u与v之间的所有整数也出现在数列中.最后由正负项均无穷多个〔即数列含有任意大的正整数及任意小的负整数就得到:每个整数在数列中出现且只出现一次.例5偶数个人围着一张圆桌讨论,休息后,他们依不同次序重新围着圆桌坐下,证明至少有两个人,他们中间的人数在休息前与休息后是相等的。证明：将座号依顺时针次序记为1,2,…,2n,每个人休息前后的座号记为,则i与j历遍完全剩余系mod2n。如果两个人,休息前后在他们中间的人数不相等,则有j2-j1≢i2-i1mod2n,即j2-i2≢j1-i1,因此,j-i也历遍完全剩余系mod2n,所以,j-i的和=≡0,而任一完全剩余系mod2n的和≡1+2+…+2n-1≡n<2n-1>≢0,矛盾！故结论成立.例6数列{an}定义为:a0=a,an+1=an+.数列{an}中存在无穷多项可被2011整除.证明:因<40,2011>=1,所以,.因当时,,所以,数列{an}构成模2011的完系,且是周期数列,所以,数列{an}中存在无穷多项可被2011整除.例7证明:存在无穷多个正整数n,使得n2+1∤n!.证明:引理1对素数p>2,存在x<1≤x≤p-1>使.证:充分性:因对1≤x≤p-1,=1,所以,,,所以,为偶数,即必要性:因1≤x≤p-1时,x,2x,…,x构成modp的既约剩余系,所以,存在1≤a≤p-1,使得ax≡-1,若不存在a<1≤a≤p-1>,a=x,使ax≡-1,则这样的a,x共配成对,则有,即为奇数,与矛盾!所以,必存在x<1≤x≤p-1>使.引理2形如4k+1的素数有无限多个.证：假设形如4k+1的素数只有n个:p1,p2,…,pn,则p1,p2,…,pn都不是a=42+1的素因数.设q是a的一个素因数,则有<2p1p2…pk>2≡-1,因存在1≤x≤q-1使2p1p2…pk≡x,即x2≡-1,所以,由引理1知,矛盾！所以,形如4k+1的素数有无限多个.回到原题:由引理1,2知,存在无穷多个素数p,使得存在x<1≤x≤p-1>使.即p|x2+1,因p>x,所以,p∤x!,x2+1∤x!,因这样的素数p无穷多,所以,相应的x也无穷多.例8设f是周期函数,T和1是f的周期且0若T为有理数,则存在素数p,使得是f的周期;<2>若T为无理数,则存在各项均为无理数的数列{an}满足0,且每个an都是f的周期.证明：<1>设T=<正整数m,n互质,且n≥2>,因=1,所以,m,2m,…,nm构成modn的完系,故存在k∈N*使得km≡1,即存在t∈N*使得km=nt+1,因f=f=f=f=f,所以是周期.设n=kp,其中k∈N*,p为素数,则是周期.故存在素数p,使是周期.<2>当T为无理数时,取a1=T,则T为无理数,0的周期,且0,且每个an都是f的周期.例9设正整数n≥2.求所有包含n个整数的集合A,使得A的任意非空子集中所有元素的和不能被n+1整除.解:设A={a1,a2,…,an}是满足条件的集合.,依题意知,对任意k=1,2,…,n都有n+1∤Sk,且任意Sk,Sj都有Sk≢Sj,所以,{Sk}包含了modn+1的所有非零剩余,因对1≤i≤n,整数ai,S2,S3,…,Sn也包含了mod的所有非零剩余,所以,a1=S1≡ai,即A中任意ai≡a1.所以,对任意1≤k≤n,a1+a2+…+ak≡ka1.且ka1≢0,从而=1.取a1=a得集合A={a+ki|ki∈Z,1≤i≤n,a∈Z,且=1}为所求.例10对任意正整数n,用S表示集合{1,2,…,n}中所有与n互质的元素之和.证明:2S不是完全平方数;例11求所有的奇质数p,使得.例12求所有质数p,使得.例13设n为大于1的奇数,k1,k2,…,kn是n个给定的整数,对1,2,…,n的每一个排列a=,记S=.证明:存在两个1,2,…,n的排列b和c,使得n!|S-S.证明:如果对1,2,…,n的任意两个不同排列b和c,都有n!∤S-S,那么当a取遍所有排列时<共n!个>,S遍历模n!的一个完系,因此,有≡1+2+…+n!≡①,另一方面,我们有=②.由①≡与②≡0<因n为奇数>矛盾!故原命题成立.例14已知m,n为正整数,且m为奇数,=1.证明:m|.证明:因1,2,…,m构成modm的完系,=1,所以2,4,…,2m也构成modm的完系,所以即.因=1,所以.得证.例15已知x∈<0,1>,设y∈<0,1>且对任意正整数n,y的小数点后第n位数字是x的小数点后第2n位数字.证明:若x是有理数,则y也是有理数.例16设A={a1,a2,…,aφ}是模n的一个既约剩余系.如果方程x2≡1在A中解的个数为N,求证:a1a2…aφ≡.同余方程与同余方程组1.同余方程<组>及其解的概念定义1给定正整数m及n次整系数多项式,则同余式f≡0①叫做模m的同余方程,若an0,则n叫做方程①的次数.若x=a是使f≡0成立的一个整数,则x≡a叫做方程①的一个解,即把剩余类a叫做①的一个解.若a1,a2均为方程①的解,且a1,a2对模m不同余,就称它们是方程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.例1解方程2x2+x-1≡0.解:取mod7的完系:-3,-2,-1,0,1,2,3,直接验算知x≡-3是解.例2求方程4x2+27x-12≡0.解:取mod15的完系:-7,-6,…,-1,0,1,…,7,直接验算知x≡-6,3是解.2.一次同余方程设m∤a,则ax≡b,叫模m的一次同余方程.定理1当=1时,方程ax≡b必有解,且解数为1.证明:因当=1时,x与ax同时遍历模m的完系,所以,有且仅有一个x使得ax≡b.即x≡a-1b.定理2方程ax≡b有解|b,且有解时其解数为,及若x0是一个特解,则它的个解是.例3解方程6x≡10.解:因<6,8>=2,且-1是一个特解,所以,方程6x≡10的解为:即.例4解方程12x≡6.因<12,9>=3,且-1是一个特解,所以,方程12x≡6的解为:即.3.同余方程组定义3给定正整数m1,m2,…,mk和整系数多项式f1,f2,…,fk,则同余式组②,叫做同余方程组.若x=a是使fj≡0<1≤j≤k>成立的一个整数,则x≡a叫做方程组②的一个解,即把剩余类a叫做②的一个解.其中m=[m1,m2,…,mk].例5解方程组.解:由例3知6x≡10的解是.所以,原解方程组或或.中国剩余定理:设K≥2,而m1,m2,…,mk是K个两两互质的正整数,令M=m1m2…mk=m1M1=m2M2=…=mkMk,则对任意整数a1,a2,…,ak下列同余式组：③的正整数解是x≡a1M1M1-1+a2M2M2-1+…+akMkMk-1.其中Mj-1满足MjMj-1≡1<1≤j≤k>,即Mj对模mj的逆.证明:<1>对1≤j≤k,因mj|Mi,mj|M,所以x≡ajMjMj-1≡aj.<2>设x,y都是同余式组的解,即x≡aj,y≡aj<1≤j≤k>,则x≡y,即mj|x-y,因m1,m2,…,mk两两互质,所以M|x-y即x≡y.注:<1>存在无穷多个整数x满足同余方程组③,这些x属于同一模m的剩余类;<2>同余方程组③仅有一个解x≡a1M1M1-1+a2M2M2-1+…+akMkMk-1.<3>当=1<=1,2,…,n>时,同余方程组仍然具有定理结论.这在数论解题中具有重要应用.例6"今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几何".解:设物数x,则有,这里m1=3,m2=5,m3=7,M=3×5×7=105,所以,35×35-1≡2×35-1≡135-1≡2,21×21-1≡21-1≡121-1≡1,15×15-1≡15-1≡115-1≡1,所以,同余方程组的解为:,即x=105k+23.例7有兵一队,若分别列5,6,7,11行纵队,则末行人数分别为1,5,4,10.求兵数.解:设兵数x,则,其中m1=5,m2=6,m3=7,m4=11,M=2310,462×462-1≡2×462-1≡1462-1≡3,385×385-1≡385-1≡1385-1≡1,330×330-1≡330-1≡1330-1≡1,210×210-1≡210-1≡1210-1≡1,所以,同余方程组的解为:,即x=2310k+2111.例8证明:对任意n个两两互质的正整数:m1,m2,…,mn,总存在n个连续的自然数k+1,k+2,…,k+n使得mi|k+i.证明:由剩余定理知,总存在整数k使得,即存在连续的自然数k+1,k+2,…,k+n使得mi|k+i.例9证明:对任意n∈N*,存在n个连续正整数它们中每一个数都不是素数的幂<当然也不是素数>.证明:因都不是素数的幂时,只能是素数之积.对任意n∈N*,取两组不同的素数p1,p2,…,pn与q1,q2,…,qn,则由剩余定理知存在m∈N*,使得同时成立.于是,n个连续正整数m+1,m+2,…,m+n中,每一个数都有两个不同的素因子.故结论成立.例10证明:存在一个含有N<≥2>个正整数的集合A,使得A中任意两个数都互质,且A中任意k个数的和都是合数.例11证明:存在一个由正整数组成的递增数列{an},使得对任意k∈N*,数列{k+an}中都至多有有限项为素数.证明:用p1,p2,p3,…表示所有素数从小到大的排列.令a1=2,a2为适合且大于a1的最小正整数a2=8,取a3适合且大于a2的最小正整数a2=38.假定a1,a2,…,an都已确定,则取an+1适合且大于an的最小正整数,由剩余定理知满足条件的an+1存在.则上述递推关系定义的数列{an}满足题意:因对任意k∈N*,当n≥k+1时,都有k+an≡0,由{an}递增可知{k+an}从第k+2项起每一项都是pk+1的倍数,且都大于pk+1,所以,数列{k+an}中至多有k+1项为素数.例12是否存在一个由正整数组成的数列,使得每个正整数都恰在该数列中出现一次,且对任意正整数k,该数列的前k项之和是k的倍数？解:取a1=1,假设a1,a2,…,am都已确定,令t为不在a1,a2,…,am中出现的最小正整数,S=a1+a2+…+am.由剩余定理知存在无穷多个r∈N*,使得成立.<如a1=1,取t=2,适合且r>1,2得r=3>.取这样的r,使得r>t且r>,令am+1=r,am+2=t,则这样得到的数列{an}满足要求.例13证明:存在一个n∈N*,使得对任意整数k,整数k2+k+n没有小于2011的质因数.例14证明:存在k∈N*,使得对任意n∈N*,数2nk+1都是合数.例15设m∈N*,n∈Z,证明:数2n可以表为两个与m互素的整数之和.
    本文档为【高中数学竞赛数论】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑， 图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
    该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
    下载需要： ￥20.0 已有0 人下载
    立即下载

    你可能还喜欢

    最新资料
    资料动态
    专题动态
    个人认证用户
    liyxi2018
    暂无简介~
    格式：doc
    大小：345KB
    软件：Word
    页数：14
    分类：建设工程
    上传时间：2022-01-31
    浏览量：5
    相关资料
    热点搜索
    上海六百商场收银员考核标准 林宥嘉—想自由—歌词 快速成型技术发展方向探讨 司机自荐书范文 大队干部推荐表 最新人教版五年级上册美术教案 中药制剂中新技术的历史沿革与现代研究与应用的发展状况 如何避免买到黄曲霉毒素超标的猫粮？ 对我国初中毕业升学体育考试的几点思考 银行同业业务现场检查要点 [精华]应用lcd1602 的自定义字库显示汉字 第四章蒙古高压特征分析 2AM-不接电话的你-音译歌词 大气污染治理工程技术导则 上海六百商场收银员考核标准 林宥嘉—想自由—歌词 快速成型技术发展方向探讨 司机自荐书范文 大队干部推荐表 最新人教版五年级上册美术教案 中药制剂中新技术的历史沿革与现代研究与应用的发展状况 如何避免买到黄曲霉毒素超标的猫粮？ 对我国初中毕业升学体育考试的几点思考 银行同业业务现场检查要点 [精华]应用lcd1602 的自定义字库显示汉字 第四章蒙古高压特征分析 2AM-不接电话的你-音译歌词 大气污染治理工程技术导则
    资料大全 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0-9
    专题大全 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0-9

    网站声明 | 侵权处理 | 投诉反馈 | 帮助中心 | 网站地图 | 爱问办公

    京ICP证000007-6 爱问文库-Copyright © 2024 版权所有

    浙公网安备 33021202002483

    客服热线：0755-26904047

    工作日：9:00-18:00

    在线客服

    • 关注爱问文库服务号