谈数论中的逆元及其应用.pdf

10中等数学谈数论中的逆元及其应用刘海涛（安徽省芜湖市第一中学，2 410 0 1）摘要：在解决数论的完全剩余系问题中，逆元是一个有利的处理工具，恰当地使用逆元可使解题过程简洁自然.在介绍逆元的定义及其常见的几个结论的基础上，通过几道例题展示逆元在解题中的使用方法，最后给出相关练习题供读者思考，体会逆元在解题中的应用。关键词：逆元；数论结论；数学竞赛；SOLO分类理论中图分类号：0 156.1文献标识码：A文章编号：10 0 5-6 416(2 0 2 3)0 4-0 0 10-0 5引用格式：刘海涛.谈数论中的逆元及其应用J.中等数学，2 0 2 3（4）：10-14.（本讲适合高中）1知识介绍1.1定义已知a、m E Z,且(a,m)=1,若存在bEZ使得ab=l(modm),则称b是a模m的“逆元”,记作b=-(modm).在不引起混淆的情况下，也可记作-l.逆元也叫数论倒数，1.2有关逆元的几个结论结论1老若a、m E Z,且(a,m)=1,则a模m的逆元一定存在.证明由(a,m)=1,结合裴蜀定理知存在x、y E Z,使得xa+ym=1,即xa=1-ym=1(modm),则x是a模m的逆元.结论2若a、m E Z,且(a,m)=1,则(al)-=.11 结论3已知a、m E Z,且(a,m)=1,若ab=ac=1(mod m),则 b=c(mod m),2 结论4已知p为素数,T=1,2,p-1).(1)若aET,则aET;(2)若a、b E T,且ab,则a-b-l.证明月（1)由x=1(modp),得=1或p-1,即1-I、(p-1)-I E T.设S=Ti1,p-1).若aES,由结论1知存在a.若a-l=1,则aa-l=丰 1(mod p);若-i=p-1,则aa-l=pa-a=p-a 丰 1(mod p).由此可得a-ES.综上,对任意的aET,有a-ET(2)不妨设ab.若2 abp-2,由(1)知a-l、b-l E S.假设-l=b-1.由 aa-l=bb-l=(mod p)=(b-a)a-=0(mod p)=pl(b-a)a-l.又(a-l,p)=1,则 pl(b-a).收稿日期：2 0 2 3-0 2-2 5修回日期：2 0 2 3-0 4-2 0基金项目：安徽省芜湖市2 0 2 2 年度教育科学研究课题基于SOLO理论的发展学生数学核心素养的实践研究（JK22019）的阶段性研究成果作者简介：刘海涛（198 8 一），男，安徽滁州人，中学一级教师，新青年数学教师工作室成员，主要从事高中数学教学和高中数学奥林匹克研究2023年第4期11于是,pb-a.而由a、b E s 得b-a3.求证：C2,-2C2PP2P证明当1hp-1时,p！Ppk!(p-k)!(P-1)!k.(k-1)!(p-1)-(k-1)!Ch-11P-iP一kPi一又=-1(mod p),于是,三Ch-11）P(mod p).三P2c.c*-2C2p-2则k=022PPP-1k=12Pk=12一(mod p).三三k=1=在模p的意义下，1(1,2,p-1)=2P-1C-2P-1故三2P(2-1p(2p-1=0(mod p).k=1k=16Nnp此题可推广至Pp,其中素数p3,mp2Pm、n E Z+,m n.例3设集合M=(1,2,10,T是M的某些二元子集构成的集合，且对T中任意两个不同的元素a,b、1x,y,都有11t(ax+by)(ay+bx).求T的元素个数的最大值.3（2 0 18，中国西部数学邀请赛）解 设a=kb(mod 11),x=ly(mod 11).若 11l(ax+by)(ay+bx),则ax+by=(kl+1)by=0(mod 11)或ay+bx=(k+l)by=0(mod 11).对1x,y/、i a,b/E T,有kl丰 1(mod 11),且k+l 丰 0(mod 1 1).由对称性，不妨设b=kla(mod 11),y=I x(mod 11).bamodm从而,ITI25.a类似地,TnM,与TM4必有个是空集.(modm）表示证明当(a,m)=1时,用=(个是空集.故TNM,与TnM,必有于是,ax+by=11by=0(mod 11),矛盾.5y(mod 11).a=2b(mod11),x(3,4),(5,9),(7,8),(10,10)分类,定义将M的所有元子集对按照(2,6),由ab,知kk即k1于是，kEM中等数学12则 by=hkrl-ax(mod 11).由 by 丰-ax(mod 11),得k-l-1(mod 11),且,k-l+I-0(mod 1 1).考虑映射 f:(a,b)(k,k).M,=1/a,b/E TI f(a,b)=(2,6)/同样定义M,、M,、M 4、M s.易得I M,I=I M,I=I M,I=I M4 I=10,IM,1=5.若TnM,与TnM，都不是空集，取a,bETnM,ix,ETnM.,则构造T=M,UM,UMs,验证2 3、2 4、63、6 4、2 10、310、410、6 10 均与-1模11不同余，符合题意，故1TImx=25.从逆元角度来看，此题本质可以理解为一种“比值”换元.例4已知a、b、n E Z+.求证：n!b a(a+b).(a+(n 1)b).证明对任意素数p(2pn),设pIln!则问题转化为证明p II.-la(a+b).(a+(n-1).记x表示不超过实数x的最大整数，(1)当plb时,88nnnn.k=1Pk=1Pp-1则n-1,从而pl1-l,(2）当p6时，由结论1,知存在c使得bc=1(mod pa).则 ca(a+b).(a+(n-1)b)=ac(ac+1).(ac+(n-1)(mod p).又n!lac(ac+1).(ac+(n-1),于是,p II ca(a+b).(a+(n-1)b).而p卜c,因此,pa Il a(a+b).(a+(n-1)b).综上,n!|b-la(a+b)(a+(n-1)b).本题很有特点，利用逆元将一个等差数列积的问题转化为连续的整数积问题.证明中用到了一个结论：任意n个连续正整数的积能被n！整除.例5设p5,p为素数,函数f,(x)=1.求证:对任意xyEZ+,当f,()-(px+k)2k=1f,()写成最简分数后,其分子是p的倍数.由题知，问题转化为证明f,()-f,(y)=0(mod p3).11又f,()-f,(y)=(px+.)(py+h)k=1(y2-*)+2 pk(y-x)(px+k)(py+h)2k=1问题可转化为证明=0(mod p).(px+k)(py+k)2k=1注意到，(px+hk)(py+k)=(2 phx+k)(2 pky+k2)=2 pki(x+y)+k(mod p).则式P(y2-x2)+2h(y-x)2=0(mod p2).2pk(x+y)+h4k=12023年第4期122pki(+y)+k44p(y-x)+2k(y-x)-3p(y-x)2 pk(x+y)+k42(y-x)3p(y?-x*)K3k3(2p(x+y)+k)知式20-P3(y2k(2p(x+y)+k)73K一k=1k=1=0(mod p2).由x、y 的任意性，式可转化为证明10(mod p2),K=（1=0(mod p).(2p(x+y)+k)k-11(p-）k=1D一1i(p-k)3k=1知式1=0(mod p).6k(p-h)3k=1又 k(p-k)=-k(mod p),故式 台0(mod p).k=1易知,式?0(mod p).三4k=1于是，原问题转化为证明0(mod p)(或0(mod p2).三k-1事实上，由拉格朗日定理知x=1(modp)至多有4个解，于是存在qE1,2,p-1,使得q 丰 1(mod p).11因为1,与92P-12P一都是模p的简系，所以，4(mod p),.k=1k=1又q 丰 1(mod p),故=0(mod p).k=l0(modp),这是因为在模p的意k=1(1,2,p-1 于是，转化为证明ki=(mod p).P-1k=1P-1p(p-1)又，式转化为证明11.32k=121(p-1),而p是奇素数,式得证.又之P，式7 转化为证明2k=121(p-1),而p是奇素数,式得证.本题选自命题人讲座（初等数论）一书，本题若不借助逆元，很难想到如何处理，这也恰恰说明了逆元在解数论题中的独到之处.练习题n+131.已知nEZ+，n 1.求满足EZ,mn-1且mn的有序整数对(m,n).n+11提示由=-1(mod n),设mn-1-1n+13kn-1(kEZ.).mn-13n+11则kn-1n+2n-1n-11=2(k-1)n(k-1)3,且1+2P.求证:p 1(m-n).pn提示由题意得11m一nn2P则n(p-1)!+(P-1!2P-1m一n(p-1)!.P注意到，上式等号左边为正整数，于是，m-n(p-1)!EZ.Pmn而(p-1),p)=1,从而,EZ.P11由 n(p-1)!2p-1=n(p-1)(1+2+.+(p-1)=n(p-1)!.P(p-1)2=0(mod p)2m-nm-nP.(p-1)!pPP因此,p I(m-n).3.已知p是素数,且p=2(mod3).求证：0,1,23,(p-1)构成模p的一个完全剩余系.提示假设存在0 i3，二是k模p的逆1元.求证：P1+22(p-1)提示注意到，P-1k=16下面证明(P-1)(2p-I)Ez即可.6由素数p3,不妨设p=6k+1或p=6k-1.若p=6k+1,则6 1(p-1),得若p=6k+1,则6 1(p-1),得(p-1)(2p-1!E Z;6若p=6k-1,则2 1(p-1),31(2p-1),得(p-I)(2p-lI E z.65.已知p是素数，p3,f(k)是k模p的逆元.求证：p1(f(1)+f(2)+.+f(p-1).提示问题等价于证明=0(mod p2),k=1即证2k=1P-1=P10(mod p2),k(p-k)k=11一11即证=0(mod p).K=1k(-k)k=1=12由练习4知上式显然成立。参考文献：1余余红兵.数学奥林匹克小丛书（第二版）高中卷.数论M.上海：华东师范大学出版社，2 0 12，7：6.2冯志刚.命题人讲座（初等数论）M.上海：华东师范大学出版社,2 0 2 2,11：7 3.32018中国西部数学邀请赛J.中等数学，2 0 19（1)：35-42.