02.从阶与原根谈起.pdf
- 文档编号:14648143
- 上传时间:2023-06-25
- 格式:PDF
- 页数:6
- 大小:260.25KB
02.从阶与原根谈起.pdf
《02.从阶与原根谈起.pdf》由会员分享,可在线阅读,更多相关《02.从阶与原根谈起.pdf(6页珍藏版)》请在冰点文库上搜索。
6中等数学从阶与原根谈起武炳杰(复旦大学数学科学学院09级,200433)中图分类号:
0156文献标识码:
A文章编号:
10056416(2012)01000605(本讲适合高中)整除与同余问题一直是数学竞赛的热点与难点本文旨在从阶出发,用原根串起一系列性质与定理,以此来解决近年来一些国内外的数学竞赛题定义1设ml,(口,m)=l,使得口暑1(roodm)成立的最小正整数称为口关于模m的阶(或指数),并用ord(口)表示定理1对于正整数。
ord(o)I营0兰1(roodm)推论lord(口)l9(m),其中,(m)是欧拉函数,表示小于m且与m互质的正整数的个数推论2若a-l(moam),-=l(moam),则口【k2)El(roodm)下面是两道利用以上性质解决的典型数论问题例1对于质数p,若对无限多个正整数尼,存在一个正整数数列几,:
,站满足:
(1)当i=1,2,k时,nt;二
(2)当i=1,2,k时,P一1是+1的倍数,与n互质,+=n,且对于i1k=1不成立此时,称P是“漂亮质数”证明:
2不是漂亮质数,但所有奇质数是漂亮质数(第23届韩国数学奥林匹克(2010)收稿日期:
20110803修回日期:
20111124【分析】可以利用阶的极小性通过设出最小质因子产生矛盾来解决此问题证明显然,n3且均为奇数记q(93)是n7,的最小质因子,不妨设gl,2由推论1知ord。
(2)I(g一1),故ord。
(2)q但由qI(2一1)及定理l得ord。
(2)lnl,这与口的最小性矛盾所以,2不是漂亮质数证明“所有奇质数是漂亮质数”略例2是否存在tN+,使得103In,2”-2(rood托)成立?
【(2010,印度国家队选拔考试)【分析】注意到,103是质数,可以通过费马小定理来找出一些有关2n的性质解不存在若存在,由费马小定理得2量1(mod103)而由题意及推论2知2兰l(rood103),、2()兰1(mod103)注意到,102=2317,且当(102,2n)=2,3,6时,经检验知不正确所以,l7l(102,2n)从而,l7ln进一步有2毫l(rood17)而由费马小定理知2E1(rood17)2012年第1期7则再由推论2知2(,)量1(mod17)同理,由于2、2莘1(mod17),则必有8I(2n,l6),进一步知4I,l,得2”-2(mod4),矛盾下面引入原根事实上,它是某些剩余系的本质刻画定义2若ord(口)=(m),则将口称作模m的一个原根定理2(原根定理)若P是奇质数,则模P的原根是存在的证明设模P的简化剩余系1,2,P一1中元素模P阶的集合为,y,取其最小公倍数=y,:
,下面证明有一根g,其阶为且y一1作标准质因数分解=卵q:
由最小公倍数的性质,知对每个s(1sj)有一个yi=aq7,而有一整数的阶为yi,取=。
易知,ord(。
)=g:
。
故剩余系中存在k个数,模P的阶分别为(l,2,k)于是,令g=注意到,阶函数的可乘性,即若(ordp(m),ordP(n)=1,则ord(啪)=ord(m)ord(n)所以,ord(g)=另一方面,因为1,2,P一1中任一数的阶均在y,y,y,中出现过,所以,兰l(modP)对=1,2,P一1成立于是,至少有P一1个解而三1(modP)不可能有超过n个不同的解,否则设Et(modP)(i=1,2,n+1),“一l-C(一1)
(一)(modp),其中,c是常数,且Pc将=代人知0三c(+l一仅1)(0c+l)(modP)因此,一定有一个(1暑,n),使得0f+1兰0。
(modP),这与有n+1个不同解矛盾所以,yp一1而由定理1及最小公倍数的性质,知l(P1),故=p一1,即ord(g)=p1下面给出一个原根作为循环群生成元的直接运用的例子,即解高阶同余方程例3已知N+,若量1(rood29),求模29的值解易验证2为模29的原根因为1(mod29)至多有7个解,而检验知2、2。
、2、2、2加、2、2。
恰好为方程不同的解,所以,方程恰好是这7个解,所求即为前面7个数模29的值下面再给出一个利用原根阶的特殊性来解决整除问题的例子例4设,z
(2)为正整数证明:
nI(+1)铮对n的任意质因数p,pI(詈-1),(p-1)-1)(2005,丝绸之路数学竞赛)证明设=Ap(p为质数)若(p一1)I(凡一1),由费马小定理易知三(凡一1)一(A-1)三-A(modp)若(p1)卜(n一1),由定理2知可取P的一个原根r由(r,p)=1,知r,2r,(P一1)r仍是一个模P的简化剩余系。
故1,卜兰()兰,l。
(np)因为(p1)、卜(凡一1),则由定理l知r。
事l(roodP)所以,Ij。
=-0(modP)同理,k毫0(InDdp)(s=2,3,)8中等数学累和得|i-o(roodp)综上,当nl(一+1)成立时,I、=l,要么(p一1)I(n一1),pI(一A+1);要么(p一1)(7,一1),Pl1第二种情形显然不可能所以,只有(p一1)I(7,一i),PI(A一1)而rl,一1=(P一1)A+(A一1),故(p一1)I(A一1),pl(A一1)反过来,若pl(A一1)PAjp,,又(p一1)I(A一1)(P一1)I(A一1)P=n一1一(P一1)(P一1)l(n一1),从而,Ii+1-1一A-0(modp)因为pn及P的任意性,所以,n(+1)事实上,利用原根还能很好地去理解二次剩余中的问题定义3定义勒让德符号(詈):
(1)当时,(詈):
o
(2)当(p,a)=1时,若兰口(modP)在简化剩余系中有解,则(詈)=1,并称。
为p的二次剩余;若耋口(m。
dP)无解,则(詈)=一1,并称a为P的二次非剩余引理设p是一个奇质数则恰有个模p的二次剩余,且恰有个模p的二次非剩余例5求有序整数对(口,6)的个数,使得+n+b=167y有整数解x,Y),其中,1口、62OO4(2004,新加坡数学奥林匹克)【分析】类似于一般的二次方程问题,可以通过配方化为二次剩余的问题解若+僦+b暑0(mod167),则配方得a一46是(2x+0)(mod167)因此,固定a后,tg一4b是模167的二次剩余故由引理知,b可取+1:
84个模167的值而=12,则每个口对应8412个b,共有20048412=2020032个有序整数解由引理能引出重要的欧拉准则定理3(欧拉准则)设P为奇质数则量(詈)(modp)证明取P的一个原根为g,故剩余系1,2,P一1可表示为g,一:
1而由引理知恰好有个二次剩余注意到,g(1后卫尹)的指数为偶数,一定是二次剩余故恰好是g的所有偶数次幂为二次剩余,奇数次幂为二次非剩余于是,当(詈)=1时,口兰()宣l(m0dp);当(詈)=一埘,毫(g2)暑誊一1(modp)最后一式是由于一三1(modp)g2鲁1(mod),而g为原根且阶为P一1,所以,只能2012年第1期9g一2E一1(roodP)正是由于模P的每个二次剩余能由P的一个原根的幂刻画,因此,很容易发现勒让德符号具有可乘性例6设P是满足P1(mod4)的奇质数计算白a-Iik2)的值(=一Ix,表示不超过实数的最大整数)(第5届中国香港数学奥林匹克(2002)【分析】首先利用前面叙述的二次剩余的性质求出分子所有的可能值,再利用取小数函数的性质,将和为整数的配成一对,求出对数即可解因为P兰1(mod4),由定理3知()=-l(m。
dp),所以,一l是模P的二次剩余由():
(寺)(),知6为二次剩余的充要条件为Pb也是二次剩余而由引理,知所有二次剩余为l2,2,()。
),故在模P的意义下,此集合等价于口l,P一口l,口,P一0当1口i一ap时,+故所求和式的值为由欧拉准则,知当P1(mod4)时,一1是模P的二次剩余;当P-3(rood4)时,一1是模P的二次非剩余利用这个性质可得到以下两个推论推论3如果整数(a,b)=1,则a。
+b的质因子都是4J+l的形式证明设P是一个质因子则a+6-0(roodP、由(口,6)=l,知(a,p)=1设c是a的模P的逆则口c兰1(modP)故(ac)+(bc)-1+(bc)-0(modP)进一步知一1是模P的二次剩余所以,P是4|l+l形式的质数推论4存在无穷多个4+1形质数证明假设只有有限个P,P:
,P令P:
(2pP2Pk)+1,取P的任一质因子g显然,g是奇数且与P,P,p均互质但P=(2plp2p)+1-0(modg),于是,一l是模q的二次剩余进一步知q也是一个4|i+1形质数所以,假设错误,原命题成立例7在整数集内,求20m一2006=40o+4,0o+2O07y的解Lo(2009,马其顿数学奥林匹克)【分析】设法因式分解后通过前述的平方和性质来证明无整数解证明原方程等价于叭。
+1:
(4瞄+2007)(Y+1)注意到,上式左边为平方和,所以,由推论3知只有4J+l形质因子而4懈+20073(mod4),故原方程无解例8证明:
有无穷多个正整数n,使得(n+1)ln!
;也有无穷多个正整数n,使得(n+1)!
f(2008,罗马尼亚数学奥林匹克)【分析】设法取一些特殊的,,将n+1因式分解为两个一次式的乘积,再进一步讨论两个一次式的最大公约数,即可构造出无穷多个符合题意的数证明对于第一个命题:
当n=2k时,n2+1:
(2一2+1)(22+2+1)因(2Ii一2Ji+1,2后+2Ii+1)=(2k一2k+1,4k)=l,而2j一2+12k=,所以,2后一2后+1是1,!
的因子10中等数学取k=5m+1,则2k+2k+1:
5(10m+6m+1)而510m+6m+12(5m+1)=n,故乘积是1:
!
的因子所以,有无穷多个n使得(,+1)l-,!
对于另一个命题,由于一l是4|iI+1形质数P的二次剩余,故存在t,(1np一1),使得PI(n+1),n0且都是质数)证明:
存在q的一个倍数,在十进制中的各位数码之和不超过3(2009,巴西数学奥林匹克)提示:
先证10模q的阶为P由定理3,知10是q的二次剩余再作g的二次剩余集合A=0u10(modg),0|ip,B;g-1u-1-10(modq),OJp这两个集合有交集,将这两个交的元素相减得到的是一个g的倍数,且可发现数码和不超过34
(1)求所有的质数P,使得1为一口一tP完全平方数;
(2)求所有的质数p,使得为完全平方数(2009,土耳其数学奥林匹克)提示:
若存在正整数和质数p满足px。
=一l,则总存在整数y、z满足下列两种情形之一:
(1)q一l=2py,g+l:
2z;
(2)9一l:
2,go-i+1:
由定理3,知当q=7时,P:
3;当q=11时,不存在P5有无穷多个8一1形质数,8Jj+5形质数提示:
若有有限多个P。
,P2,P,仿照推论4的证明,对8一1形证P=(PlP2p)一2有满足的质因子,对8+5形证P=(p1P2,P)+4有满足的质因子参考文献:
1第23届韩国数学奥林匹克(2010)J中等数学,2011(增刊)22010印度国家队选拔考试J】中等数学,201I(增刊)132005丝绸之路数学竞赛J中等数学,2006(增刊)42004新加坡数学奥林匹克J中等数学,2005(增刊)5第5届中国香港数学奥林匹克(2002)J中等数学,2004(增刊)62009马其顿数学奥林匹克J中等数学,2OlO(增刊)72008罗马尼亚数学奥林匹克J中等数学,2OLO(增千II)从阶与原根谈起从阶与原根谈起作者:
武炳杰作者单位:
复旦大学数学科学学院09级,200433刊名:
中等数学英文刊名:
High-SchoolMathematics年,卷(期):
2012
(1)本文链接:
http:
/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 02. 谈起