首页 竞赛专题--欧拉定理、费马小定理、孙子定理

竞赛专题--欧拉定理、费马小定理、孙子定理

竞赛专题--欧拉定理、费马小定理、孙子定理竞赛专题--欧拉定理、费马小定理、孙子定理欧拉定理、费马小定理、孙子定理 1、设m0，则模m有m个剩余类M{ikm|kZ},i0,1,2,？,m1,,，,,,i ,如果i与m互质，那么M中每一个数均与m互质，这样的同余类共有(m)个, i ,(m)是1，2，？，m中与m互质的个数，称为欧拉函数; ,(m) 2、欧拉定理:设m,1，(a,m),1,则a,1(modm);3、缩系的几种性质: ,(1)、模m的一组缩系含有(m)个数; ,,(2)、若a、a、？a是(m)个与m互质的整数，则a、a、？a是模m的一组缩系...

竞赛专题 --欧拉定理、费马小定理、孙子定理欧拉定理、费马小定理、孙子定理 1、设m0，则模m有m个剩余类M{ikm|kZ},i0,1,2,？,m1,,，,,,i ,如果i与m互质，那么M中每一个数均与m互质，这样的同余类共有(m)个, i ,(m)是1，2，？，m中与m互质的个数，称为欧拉函数; ,(m) 2、欧拉定理:设m,1，(a,m),1,则a,1(modm);3、缩系的几种性质: ,(1)、模m的一组缩系含有(m)个数; ,,(2)、若a、a、？a是(m)个与m互质的整数，则a、a、？a是模m的一组缩系()12m12m的充要条件是a,a(modm),(i,i);ii (3)、若(a,m),1,且x是通过模m的缩系，则ax也是通过模m的缩系; p4、费马小定理:若p为素数，则a,a(modp); ,,,k125、若n的标准分解为:n,pp？p，则:12k 111,(n),n(1,)(1,)？(1,)ppp12k 6、孙子定理:设m、m、？m是k个两两互质的正整数，设m,mm？m,m,mM,1212kkii (i,1,2,？,k),M,mm？mm？m,则同余方程组,，1211iiik x,b(modm)11 x,b(modm)22 ？？ x,b(modm)kk '''有唯一解x,MMb，MMb，？，MMb(modm)111222kkk '其中MM,1(modm),i,1,2,？,kiii 例1、设a、a、？a和b、b、？b分别是n的一组完全剩余系，且2|n，nn1212 求证:a，b、a，b、？a，b不是n的一组完全剩余系。nn1122 证:？a、a、？a是n的一组完全剩余系，则:n12 nnn(n，1)na,i,,(modn),,选自《奥林匹i22ii,1,1克数学》高三nn61 分册P同理有:b,(modn),i2i,1 n ？(a，b),n(modn),0(modn),iii,1 又？另一方面(a，b)也是一组完全剩余系，则有:ii nn(a，b),(modn),ii2i,1 n？2|n,0,,n,？上式不成立，？原命题成立; 2 1 n例2、证明:数列{2,3}中有一个无穷子数列，其中任意两项互素; n证明:设数列{2,3}中已有k项是两两互素的，记为u,u,？,u,k12,uuu()，1？12k作u,2,3k，1 选自《奥林匹克数学》高,其中(x)是欧拉函数，由欧拉定理有: ,,,,uuuuuu三分册P63 ()((()？))？12k12k2,2,1(modu),1,i,ki uuu,(？)，112k？2,3,,1(modu),1,i,ki ？？数列u,u,,u、u是k，1项两两互素的子数列，依此方法一直下去12kk，1 n数列{2,3}中一定有一个任意两项互素的无穷子数列{u}i ,,,,选自《数学31,2,pp(p),p例、在？中有多少个数是与互质，并求为素数。竞赛研究教p解？为素数程》上册P154 ,,,？问题即为:1,2,？p中有多少个数是与p互质，并求(p) ,,,,1,1 pp,p,p,pp,pp又？在1,2,？中是的倍数有:1，2，3，？，共有个其他的数均与互质p 1,,,,1,,()(1)？p,p,p,p,p 1 【练习】证明:,(4),n不可能成立;4 4例4、证明当素数p,7时，p,1能被240整除;选自《世界数学奥林匹证:？素数p,7,？p是奇数克解题大辞典》数论卷 42P343 又？p,1,(p,1)(p，1)(p，1) 2且p,1,p，1,p，1均为偶数，p,1和p，1是相邻的偶数，则: 42p,1,(p,1)(p，1)(p，1)能被2,2,4,16整除又？费马小定理有:(3,p),1,(5,p),1 24？3|p,15|p,1 4又？16，3与5两两互素，则16,3,5|p,1 4？240|p,1 13 【练习】证明:2730|n,n,(n,N) 2 例5、设m和n是自然数，满足:对任意自然数k，11k,1与m和11k,1与n具有相同 l的最大公约数，证明存在某个整数l，使m,11n。 ij证:设m,11p,n,11p,其中i,j为非负整数，且11|p,11|q l为证明存在某个整数l，使m,11n，只需证明p,q 假设p,q, ？(p,11),1,？由孙子定理有:存在正整数a，使得:a,0(modp) a,,1(mod11) ？a,11k,1,(k,N),且11|a选自《世界数学奥林匹i又？(11k,1,m),(a,11p),p克解题大辞典》数论卷j(11k,1,n),(a,11q),q,p368 P 另一方面:(11k,1,m),(11k,1,n) ？产生矛盾，假设不成立，同理p,q也不成立 i,j ？p,q即:m,11n,l,i,j 【练习】是否存在1000000个连续整数，使得每一个都含有二重的素因子，即能被某个素数平方所整除。 3 ,选自《数学1【练习】证明:(4),n不可能成立;竞赛研究教4 程》上册P155 1,证:若(4),n成立，则4|n4,,,,,k122,(2),,,设n,ppp,ppp为奇质数，则:？？12k12k p,111p,p,1,,,,,,,,k,12kk1212()22()()()n,ppp,ppp？？？12k12k 4ppp12k ,,,1,,,,1,,1,,2,kk1212即:2ppp,2ppp(p,1)(p,1)(p,1)？？？12k12k12k即:ppp,4(p,1)(p,1)(p,1)？？12k12k 又？上式右边是一个偶数，左边是一个奇数，？上式不成立，？假设不成立 1？,(4),n不可能成立4 13【练习】证明:2730|n,n,(n,N) 13证明:？2730,2,3,5,7,13，若记f(n),n,n,(n,N),则由费马小定理，可知13|f(n),选自《中国 1366华罗庚学校由于n,n,n(n,1)(n，1) 336数学课本》 ,n(n,1)(n，1)(n，1) P218 226,n(n,1)(n，1)(n，n，1)(n,n，1)(n，1) 7532故f(n),n,n,f(n),n,n,f(n),n,n,f(n),n,n,都是f(n)的因式1234 由费马小定理可知:7|f(n),5|f(n),3|f(n),2|f(n)1234 即2，3，5，7，13均整除f(n),且2，3，5，7，13两两互素，故2730|f(n) 【练习】是否存在1000000个连续整数，使得每一个都含有二重的素因子，即能被某个素数平方所整除。？证明:令p,p,p是s个相异的素数，由孙子定理，下列同余式组12s 2x,,1(modp)1选自《世界数学奥林匹2x,,2(modp)2克解题大辞典》数论卷？？P360 2x,,s(modp)存在一解，设此解为ns 2？则s个连续整数n，1,n，2,,n，s每个都有一个二重素因子，即有p|n，ii 取s,1000000,则可得到满足条件要求的1000000个连续整数; 4 5

                    本文档为【竞赛专题--欧拉定理、费马小定理、孙子定理】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

竞赛专题--欧拉定理、费马小定理、孙子定理

你可能还喜欢