首页 比赛专题--欧拉定理、费马小定理、孙子定理[教学]

比赛专题--欧拉定理、费马小定理、孙子定理[教学]

比赛专题--欧拉定理、费马小定理、孙子定理[教学]比赛专题--欧拉定理、费马小定理、孙子定理[教学] 欧拉定理、费马小定理、孙子定理 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,12k12kii (i,1,2,？,k),M,mm？mm？m,则同余方程组,，i12i1i1k 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，12n12n 求证:a，b、a，b、？a，b不是n的一组完全剩余系。1122nn 证:？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 n例2、证明:数列{2,3}中有一个无穷子数列，其中任意两项互素; n证明:设数列{2,3}中已有k项是两两互素的，记为u,u,,u,？k12,uuu()，1？12k作u,2,3k，1 选自《奥林匹克数学》高其中(x)是欧拉函数，由欧拉定理有:, 三分册P63 ,,,,uuuuuu()((()？))？12k12k2,2,1(modu),1,i,ki uuu()，1,？12k？2,3,,1(modu),1,i,ki ？数列u,u,,u、u是k，1项两两互素的子数列，依此方法一直下去？12kk，1 n数列{2,3}中一定有一个任意两项互素的无穷子数列{u}i ,,,,选自《数学pppp31,2,(),例、在？中有多少个数是与互质，并求为素数。竞赛研究教p解？为素数程》上册 P154 ,,,？ppp1,2,()问题即为:？中有多少个数是与互质，并求 ,,,,1,1pp,p,p,pp,pp1,2,123又？在？中是的倍数有:，，，？，共有个 p其他的数均与互质 1,,,,1,？p,p,p,p,,()(1)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) 例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个连续整数，使得每一个都含有二重的素因子，即能被某个素数平方所整除。选自《数学,1【练习】证明:(4),n不可能成立;竞赛研究教4 程》上册P155 ,1证:若,n成立，则n(4)4|4,,,,,k12？？设n,2ppp,(,2),p,p,p为奇质数，则:12k12k p,1p,p,111,,,,,,,,,k12kk1212？？？n,ppp,ppp()22()()()12k12kppp412k ,,,,,,,,,,,,1112kk1212？？？即:2ppp,2ppp(p,1)(p,1)(p,1)12k12k12k ？？即:ppp,4(p,1)(p,1)(p,1)12k12k ？又上式右边是一个偶数，左边是一个奇数，？上式不成立，？假设不成立 1？,,n不可能成立(4)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 2P克解题大辞典》数论卷选自《世界数学奥林匹360 x,,1(modp)1 2x,,2(modp)2 ？？ 2x,,s(modp)存在一解，设此解为ns 2？则s个连续整数n，1,n，2,,n，s每个都有一个二重素因子，即有p|n，ii 取s,1000000,则可得到满足条件要求的1000000个连续整数;

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

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

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

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

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

立即下载

比赛专题--欧拉定理、费马小定理、孙子定理[教学]

你可能还喜欢