一次同余方程的解法及在中学数学竞赛中的应用初探

(2014)届本科生学年论文题目一次同余方程的解法及在中学数学竞赛中的应用初探专业数学与应用数学院系数学与计算机科学学院学号100802014310080201271008020147姓名彭莎任莎莎胡益梅指导教师唐再良教授目录1.同余的基本理论知识……………………………………………………11.1同余的定义…………………………………………………………….11.2同余的定理…………………………………………………………….12.一次同余方程的几种解法…………………………………………………22.1验根法…………………………………………………………………..22.2利用二元一次不定方程……………………………………………22.3利用辗转相除降模……………………………………………………33.同余理论在数学竞赛中的应用…………………………………………..43.1分类法…………………………………………………………………..43.2奇偶分析法…………………………………………………………….43.3构造法…………………………………………………………………..53.4枚举法……............................................................................73.5反证法……............................................................................8参考文献……………………………………………………………………….10一次同余方程的解法及在中学数学竞赛中的应用初探-1-一次同余方程的解法及在中学数学竞赛中的应用初探【摘要】：介绍一次同余方程的几种解法，并了解一次同余方程的解法在中学数学竞赛中的应用。【关键词】：一次同余方程解法数学竞赛中的应用1.同余的基本理论知识1.1同余的定义定义1：设,ab为整数，m是一个正整数且0a（modm），则称(mod)axbm为模m的一次同余方程。定义2：若0x是使(mod)axbm成立的一个整数，则x0x（modm）称为一次同余方程(mod)axbm的一个解。1.2同余的定理定理：一次同余方程(mod)axbm，0a（modm）有解的充要条件(,)|amb,且有解时解数为(,)am。一次同余方程的理论各初等数论教材都作了详细的论述（见[1]）、[2]、[3]），但对它的具体解法介绍的较少。笔者在初等数论教学实践中，针对该方程总结了几种解法，并通过各种解法优劣的比较，探讨了在不同情况所应采用的不同方法，这对学生学习初等数论，特别是解一次同余方程具有一定的指导作用。一次同余方程的解法及在中学数学竞赛中的应用初探-2-2.一次同余方程的几种解法2.1：验根法由定义2可以看出，求一次同余方程(mod)axbm，有几个解，有哪些解，只需取模m的一个完全剩余系（如0,1,2，…，m-1）中的每一个数，将其代入同余方程中逐一验证，即可求出其全部解。例：解同余方程62(mod8)x解：取模8的最小非负数完全剩余系0,1,2,…,7,分别代入同余方程62(mod8)x中知3,7xx满足同余方程。故原同余方程的解为：3(mod8),7(mod8)xx。分析：验根法需对模m完全剩余系中的数逐一验证，因而当模m比较小的时适用于此法。2.2：利用二元一次不定方程满足的和满足二元一次不定方程方程的相同，因而解可利用二元一次不定方程来求。例：解同余方程.解：先解不定方程，即。用观察法或辗转相除法可得其一组解为,.所以不定方程的一次同余方程的解法及在中学数学竞赛中的应用初探-3-所有解为满足的所有整数位…)故原同余方程的解为：.2.3：利用辗转相除法降模例：解同余方程1230(mod45)x.解：1230(mod45)4530(mod12)36(mod12)126(mod3)0xyyzz0(mod3).这表明最后一个同余方程有3个解0,1,2(mod3).z逐次反向推导得出关于y对模12有3个解：61224(mod12)3zyz（z=0,1,2）关于x对模45有3个解：30453090180515(mod45)1212yzxz（z=0,1,2）即原同余方程解：5,10,25(mod45).x分析：这种方法适用于所有一次同余方程，且如果方程无解，则在某一步可直接看出，不用求a与m的最大公约数。但要注意利用同余式性质化简用余方程时，若改变同余方程的模，则要注意方程的解数。一次同余方程的解法及在中学数学竞赛中的应用初探-4-3．同余理论在数学竞赛中应用数学奥林匹克竞赛中的初等数论问题，着重考察富于创造性、灵活性的方法技巧：分类法、奇偶分析法、构造法、枚举法、反证法等．下面我们通过一些典型的例题来探讨用同余理论解答数学奥林匹克竞赛的题目．3.1分类法分类法是将题中符合条件的情况合理分类讨论，分别得出结果，再将结果汇总得到最终结论的方法。例1求使能被3整除的一切自然数n.解：因为，所以.则所以当n为奇数时，能被3整除;当n为偶数时，不能被3整除3.2奇偶分析法整数可以分为两类：奇数与偶数．利用奇数与偶数的分类及其特殊性质，可以简单快捷地求解一些与整数有关的问题，我们把这种通过分析整数的奇偶性，分情况讨论，从而解决问题的方法称为奇偶分析法．例6设,,abc是三个整数，证明在三个数()(-)ababab，()(-)bcbcbc，()(-)cacaca中至少有一个是24的倍数．一次同余方程的解法及在中学数学竞赛中的应用初探-5-思路分析本题要证明三个数中至少有一个是24的倍数，24可以分解为2483，且(3,8)=1，又因为,,abc均为整数，则必有两个数奇偶性相同，那么可以假设,ab奇偶性相同，由此利用数的奇偶性来分情况讨论，由此解答题目．证明因为,,abc均为整数，则必有两个数奇偶性相同，不妨设,ab奇偶性相同．下面证明24|()(-)ababab因为2483且(3,8)=1，因此只须证明3|()(-)ababab且8|()(-)ababab若,ab中至少有一个是3的倍数时，则有3|()(-)ababab；若,ab均不是3的倍数，则,ab是用3除余数分别为1和2．当(mod3)ab，则3|-ab，从而3|()(-)ababab；当(mod3)ab同余时，则3|ab，则3|()(-)ababab．因此对任意整数,ab均有3|()(-)ababab．若,ab均为偶数时，显然8|()(-)ababab；当,ab均为奇数时，显然ab，-ab均为偶数，且,ab用4除，余数分别为1和3，当(mod4)ab，则4|-ab；当(mod4)ab时，则4|ab，所以8|()(-)ababab．综上所述，当,ab奇偶性相同时24|()(-)ababab，即三数()(-)ababab，()(-)bcbcbc，()(-)cacaca中至少有一个是24的倍数．3.3构造法解数学题时，根据问题的性质和结构特征，联想与此有关的数学知识，精心地设计一些特殊的“构造”（辅助模型），通过对这个辅一次同余方程的解法及在中学数学竞赛中的应用初探-6-助模型的的研究，便可把陌生的问题转化为熟悉的问题，把未解决的问题转化为已解决的问题，从而使问题获得解决．这种解决问题的方法就叫做构造法．构造思想贵在“创新”，解题时要打破常规，另辟蹊径，表现出简捷、明快、精巧等特点．例7求141414的末尾两位数．思路分析本题看上去十分繁琐，让人无从下手．题意要求141414的末尾两位数，即求与141414关于模100同余的数，模100又可分解为254，可以先求与214关于模25同余的数，再逐步求出与1414关于模25同余的数，然后利用同余的性质，求得最后答案．解令141414A，欲求A的末尾两位数，即求a，使得(mod100)Aa，由于100254，则1414140(mod4)A①2141964(mod25)，6314(4)6414(mod25)，由于(14,25)1，故5141(mod25)，则10141(mod25)．对于4(1,2,)nn…，当n为奇数时，4n的个位数字为4；当n为偶数时，4n的个位数字为6．同理1414的个位数字应为6．故可设1414106,(Z)tt，从而得到：106106514(14)14114141141411(mod25)tttA，即11(mod25)A②由②得2511,(Z)Ayy，代入①得一次同余方程的解法及在中学数学竞赛中的应用初探-7-25110(mod4)y，30(mod4)y，1(mod4)y，从而有，41,(Z)ykk，于是，25(41)1110036Akk．所以，141414的末尾两位数是36．3.4枚举法在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．特点：将问题的所有可能的答案——列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃．例8①对于模15，找出一组由奇数组成的完全剩余系和一组由偶数组成的完全剩余系．②对于模15，找出一组由奇数组成的简化剩余系和一组由偶数组成的简化剩余系．思路分析本题的考查目的比较单一，就是考查剩余类和剩余系的定理”设m为正整数，(,)1am，b是任意整数，若x通过模m的一个完全剩余系，则axb也通过模m的完全剩余系”，列出完全剩余系之后，再采用枚举法令,ab取适当的值，即可求得符合题意的剩余系．解①因0,1,2,3,,14…是模15的一个完全剩余系，取2,1ab，则(,15)a1，则201,211,221,2141…,，即1,3,5,7,,29…是模15的一组由奇数组成的完全剩余系．同理，取2,2ab，则202,212,222,,2142…，即2,4,6,,30…是模15的一组由偶数组成的完全剩余系．一次同余方程的解法及在中学数学竞赛中的应用初探-8-②因1,2,4,7,8,11,13,14是模15的一组非负最小简化剩余系，取2a，则有21,22,24,28,211,213,214，即2,4,8,14,22,26,28为模15的一组由偶数作成的简化剩余系．又因1,3,5,7,,29…是模15的一组完全剩余系，从中找出与15互素的所有数，为1,7,11,13,17,19,23,29，则此为模15的一组由奇数组成的简化剩余系．3.5反证法证明一个命题，如果把原结论的相反结论纳入到原命题条件中，由此经过正确推理，推导出和已知证明的定理、公理、题设等相矛盾的结果，或以两个不同的角度进行推理所得出的结论之间相互矛盾，那么即可肯定原来的结论成立，这种间接证明命题的方法叫做反证法．例9求证不定方程44412141599xxx…无整数解．．思路分析如果直接求不定方程无整数解，会比较繁琐，那么就从本题的反面来思考，如果不定方程有整数解，那么带入原方程就应该成立，再通过一系列证明，即可得出矛盾，从而得证．解15991600-1-115(mod16)设1214,,,Zxxx…是方程的整数解，若2ixn，则44160(mod16)ixn；若21ixn，则44(21)ixn43216322481nnnn一次同余方程的解法及在中学数学竞赛中的应用初探-9-4316(2)8(31)1nnnn1(mod16)显然有4441214(mod16)xxxa…，14a，与4441214159915(mod16)xxx…矛盾．因此，此方程无整数解．一次同余方程的解法及在中学数学竞赛中的应用初探-10-参考文献[1].闵嗣鹤,严士健.初等数论[M].北京：