费马小定理应用篇

《费马小定理应用篇》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、费马小定理应用2篇18费马小定理应用2篇18以下是网友分享的关于费马小定理应用的资料2篇，希望对您有所帮助，就爱阅读感谢您的支持。费马小定理应用篇16中等数学费马小定理和欧拉定理的应用王连笑(天津市实验中学．300074)中图分类号：0156文献标识码：A文章编号：1005—6416(2010)11—0006—05(本讲适合高中)费马小定理和欧拉定理是数论中非常重要的两个定理，对解决整除问题和同余问题有着强大的功能，因此，也是数学奥林匹克命题的一个丰富宝藏．与费马小定理和欧拉定理有关的题目是国内外数学竞赛命题中出现频率十分高的一类问题．本文先介绍与此有关的一些知识，所涉

2、及的定理及结论可以在任何一本数论书中找到证明，不再赘述，然后通过几个例题介绍这两个定理及有关知识的应用．1基础知识1．1欧拉函数妒(m)(1)欧拉函数妒(m)的定义：p(m)表示对正整数m，数列0，l，…，trt—l中与m互质的数的个数．例如，妒(1)=l，妒(5)=5，tp(10)=4(与10互质的数为l、3、7、9，共4个)．(2)欧拉函数妒(m)的性质．(i)欧拉函数妒(m)是积性函数，即若(a，b)=l，则tp(口6)=妒(口)妒(6)．(ii)若P是质数，则9(p)=p—l，9(p‘)=p‘一p‘一1．(iii)设m=硝1p；2．p：‘18，其中，Pi(i=l

3、，2，…，k)为不同的质数．则9cm，=m(一去)(一壶)…(一去)．(iv)设dl，d2，…，dr(。)是正整数m的所收稿日期：2010一cr7—28有正约数．则∑妒(盔)=J，I．例如，m=12，其正约数为l、2、3、4、6、12，而9(1)+妒(2)+妒(3)+妒(4)+9(6)+妒(12)=l+l+2+2+2+4=12=l,]rt．1．2欧拉定理对每个整数，l>l和一切与／’t互质的正整数口，都有a中‘4’兰l(modn)．1．3费马小定理设P是质魏若(口，P)=1，则口P。1兰1(modp)．1．4威尔逊定理设P是质数．则(p—1)!毫一1(modp)．1．5

4、阶数和原根(1)定义．当(口，m)=l时，有最小正整数坡a“兰l(modm)，且口‘18≠l(modm)(

5、i}=1，2，…，A—1)．则A称为口关于m的阶数．由欧拉定理显然有A≤妒(m)，

6、：119(m)．如果A=9(m)，即口关于m的阶数是妒(m)，则称a为m的原根．例如，口=3，m=10，tp(10)=4，由于31=3，32=9，33=27，34：81量l(II稍10)，3关于10的阶数是妒(10)=4，3是lO的又如，a=3，m=8，妒(8)=4，由于32=9暑l(mod8)，2是3关于8的阶，而3不是8的原根．则原根．则2010年第11期因为任何奇数的平方关于

7、模8都与l同余，所以，8的原根不存在．(2)性质．(i)如果a关于m的阶数是A，则a1，a2，…，a卜1中的任何两个数对m不同余．(ii)若A是a关于m的阶数，则a‘兰l(modm)僦It．2例题选讲例l证明：若(a，b)=l，P为质数，且PI(a2+b2)，贝4p事一l(mod4)。证明用反证法．假设P=4k—l(k∈N+)．由(a，b)=1，则口、b不可能都被P整除．(1)当a和b恰有一个能被P整除时，不妨设PI口，P’18b，则p卟b2等p斗(a2+b2)，矛盾．(2)当a和b都不能被P整除时，由费马小定理有PI(aPl一1)，PI(bP‘一1)．故PI(a9～一

8、b9一)，即PI(a“一2一b4k-2)．又p十6，则P’b4k-2=印卟264‘一2．于是，p、卜(a础≈+b“。2)，即P、卜(a2+62)(n础一4+∥一6b2+…+6驰一4)．因此，P斗(a2+b2)，矛盾．所以，a2+62没有4．j}一l型的质因数．【说明】本题表明两个互质的平方数之和的奇质因数一定是4后+l的形式．下面的两个例题是这一结论的应用．例2在整数集里，求名2010一200618=4户啷+4矿嘲+2007，，的解．…(2009，马其顿数学奥林匹克)解原方程化为茗2010+l=4v2009+4，懈+2007y+2007=(4y2懈+2007)(Y+1)

9、．由于4广啷+2007三一l(mod4)，则4广懈+2007必有4后一l型的质因．而(茗，1)=l，则x2010+1没有4I

10、}一l型7的质因数，矛盾．所以，本题无解．例3证明：方程x2+5=y3没有整数解．(1979，保加利亚数学奥林匹克)证明假设方程有整数解(石，)，)．(1)当菇为奇数时，则髫2+5---2(mod4)．于是，y3--2(mod4)．因此，Y是偶数，即y-0(mod2)．因而，Y3三0(mod4)，矛盾．(2)当x为偶数时，设x=2n．由广=矿+5-1(rood4)，则y-1(mod4)，可设Y=4m+1．原方程化为