下载文档原格式
详析一次同余式求解定理的证明教学方法详析一次同余式求解定理的证明一[摘要]一次同余式求解定理的证明,在各版本的数论课本中均有介绍,但跳跃性都比较大,使读者在学习过程中会有很多疑问,本文就该定理给出详细的思路分析与证明过程. [关键词]一次同余式证明概念,定理介绍同余方程定义1设m是正整数,f(x)为n次多项式厂()=a+口一】+…+口I+口0其中口f是正整数,则f(x)-O(1)叫做模m的(n次)同余式,n叫做厂()的次数,记为degfo如果整数a使~-f(a)-O(modm)成立,则a叫做(1)式的解.(1)的解a常写/~x=a(modm),在模m的完全剩余系中,使得(1)成立的剩余个数叫做同余式(1)的解数.定理设m是一个正整数,a是满足aCEm的整数.则一次同余式ax-b(modm)有解的充分必要条件是(a,m)b.而且,当该同余式有解时,其解数为,).该定理的证明需要用到的先知定理,在此不加证明地将它们作为引理罗列如下:引理1设a,b,c≠O是三个整数,若cIa,clb,则对于任给的整数S,t均有clsa+tb引理2设m是一个正整数,a-b(modm),k>0,则ak=bk(modmk)引理3设m是一个正整数,a,a2,b.,b2是四个整数.如果al-bl(modm),a2-b2(modm)贝0:(i)a十口2-bI+62(modm):(ii)a1+口2兰6l+62(modm).引理4设m是一个正整数,a是满足(a,)=l的整数,则存在整数d1口<m使得aa三1fmodm)引理5设m是一个正整数,a--b(modm),如果整数(口,b,),则ab(m0)引理6设m是一个正整数,口bd(modm),如果()=1,则口一b(modm)思路分析定理的征明分为两个部分,第—部分需要{正明b(modm)有解的充分必要条件是(口,m)lb;第二部分需要证明有解的情!I!:绝况,膦效为dⅡ,州.第一部分中,必要性的证明比较简单,主要分析充分性的证明,即证明当(口,m)lb时,ax=--b(mod)有解.直接证明不太容易,通常可采用构造法构造出一个解即可.但直接构造出饿一b(modm)的解也很困难,不妨考虑如下三个形式类似的同余式ax-=b(modm)(1.1);m0d)(1_2)i删J【J(mod)(1_3)若(1.2)式有陬;m.d),即?(肌)d(),由引理2可知,因为>0,故甄一6(m,xtm),即说明t(modm)~(1.1)式的—,解.而要构造出(1.2)式的解t(m.d),则可从(1.3)式入手.若(1.3)式有解m喃),即m喃),她mod1,故由引理3(ii)式可知兰odJ,砹田与l埋LJ瓦口J划ab;,m0di-J,则说;知i=.d)是(12)式的解.对于(1-3)式,由于(,1,由引理4可知必存在使得l(m.d成立,&一十.d)是(1.3)式的一个解.通过上面分析可以看出,(1.3)式必有解m0d),由此可构造出(1.2)式的一个解,;m,进而可推断;oa,b(mod必是(1.1)式的一个特解.构造性证明成立.第二部分,需要证明(1.1)式在有解的前提下,解数为(a,).由剩余类的定义可知,模m的剩余类有Co,C,…一一共m个.这里可先求出(1.1)式所有解的表示形式,再证明所有的解只能属千樽m的l余类中的(口,)个广教学方法证明过程第一部分设同余式(1.1)式有解rXo(m,即满足0三6(nxxt 神,根据同余的定义知,存在整~O.V o使得aXo——myo=b因为(a,m)la,(日,)l坍,根据引理1,(口,m)laxo—myo=b因此,必要性成立;充分性已知(a,m)Ib,则为整数?首先+我们考虑同余式(1.3)南in)因为(,】,由引理4可知存在蝴1(m成立,&响)是(1_3)式的一个解.事实上,同余式(1.3)不仅有解,而且解数唯一.因为如果同时有同余式a(m和(m成立.两式相减得到一xo)----0(m)因为,,撇引理6,(x-xO,即任一解z与x.位于模!的同—剩余类,~lk-=x如响). 其次,考虑同余式(1.2)门已始出衡导㈣,即南0三,而又显然有Ⅱx)di=『-)成立,故由引理3的∞式可知x.z),则说吼=‰b|-‰_J,则谠一‰(rn(x(12)式的解.仿上,亦可证该解的唯—性.最后,考虑同余式(1.1)Eb(modm)(1.2)式有,(rr,壮m吗,(上接第123页)又因为(口,)>0,由引理2可知,ax;b(modm).即说明X~--’X0西幌(1.1)式的—个特解.这样,充分性成立. 所以,饿b(modm)有解的充分必要条件是(口,m)lb. 第二粉首先,给出同余式(1.1)饿b(modm)任一解的表示形式.~x---x(modm)是(1.1)式的一个特解,贝与任—解玢别满足饿1b(modm)和饿￡b(modm)由同余的传递性可知,axt;ax(modm),即日～Xt);0(modm),又因为(口,m)la,0,,由引理5可响J0(泣,同时又因为,:1,由引理6可得(r-x~0,一,由同余的概念可知,任一解坷表示为t+m,其中,,为任意整数,I]1]ax=-b(modm~全部解为xXt+f(modm),f为任意整数;下面,根据解数的概念,证明(1.1)式的全部解只能属于模m的剩余类中的(口,)个.取模的一个完全剩余系x,x+1,…,X,+一1),对于(1.1)式的全部t+f,不妨让0,1,2,…,计靴能取到上面完全剩余类的个数.当t:0时,E(moa’n);…,当t=(口,)时,i+~----XI(m0d,.故f需要满足x一≤t+<,+,即o≤k(口,).由此可知,f的取值共(口,)个,即同余式(1.1)的解数为(a,)个.证毕.参考文献t陈恭亮.《信息安全数学基础》,上海交通大学,2004作者单位:陕西广播电视大学学习支持服务中心西安电子科技大学方面的专家,而来自学员单位的兼职导师则具有丰富的临床实践经验,他们可以对研究生的课题进行深入的理论分析和科学的实验指导.6.制定医学非全日制研究生学位论文的评价标准医学非全日制研究生的学位论文应该有自己的特色,学员要在导师指导下,充分利用学校,单位的仪器设备,技术力量,资金等各自的优势,发挥两者的长处,解决本单位的具有一定经济效益或社会效益的临床工作和管理方面的问题.非全日制研究生的学位论文,应注重其是否反映作者较好地掌握了基础理论和专门知识,能够综合运用科学理论,方法和技术手段解决实际问题的能力.参考文献t…张卫刚,谢仁业,马桂敏等.非全日制研究生教育亟待规范[J】.学位与研究生教育,2003.(O3).【2】钟尚科,张卫刚,杨颉域谈规范发展非全日制研究生教育[J].高等教育研究,2002,(06).【3]扬颉,张卫刚_我国非全日制研究生教育的发展与问题[J].现代大学教育,2001,(06).[4】昊环伟.严把”四关”确保j}全日制研究生教育质量【J].中国高等教育,2003.(21).【5】张大鹏,张元,罗旋辉等.探索医学成人教育教学与管理新模式[J】冲国成人教育,2006,(1O).作者单位:南通大学医学院。
人教版高中选修(B版)4-63.2一次同余方程教学设计一、教学目标1.掌握一次同余方程的概念及解法。
2.能够熟练运用一次同余方程解决实际问题。
3.培养学生的数学思维能力和逻辑思维能力。
二、教学内容一次同余方程的概念及解法。
三、教学重点和难点•重点：熟练掌握一次同余方程的解法。
•难点：将一次同余方程应用到实际问题中。
四、课前准备1.教师准备课件和教学材料。
2.学生预习一次同余方程的基本知识和相关概念。
五、教学过程1.导入：教师简单介绍一下本节课要学习的内容，并且通过引导学生解决一个实际问题，引出本节课的主要内容。
例如：小明爸爸想买两个相同的项链送给他的孪生姐妹，但是他只能去一次商店，他需要知道商店铺面上的项链数量是不是1、3、5、…100中的一个数字。
请问商店总共有多少条项链？2.新知：介绍一次同余方程的相关概念和解法，并通过一些例题让学生熟练掌握解题方法。
例如：（1）求x满足同余方程$7x\\equiv 5 \\pmod{18}$.解：因为$\\gcd(7, 18) = 1$，所以可以直接使用扩展欧几里得算法求解：$$\\begin{aligned} 7x + 18y &= 1 \\\\ 7 \\times 5 - 18 & = 1 \\end{aligned}$$所以$x\\equiv 5\\times 7^{-1}\\pmod{18}$，其中$7^{-1}\\equiv 13\\pmod{18}$，所以$x\\equiv 65\\equiv 11\\pmod{18}$.3.实践：让学生通过实际问题解决一次同余方程。
例如：某社会团体欲向所有会员发放纪念章，发放数量应该是最少的，同时还需要跟会费缴纳额挂钩。
设会费是5元、9元、15元中的一个，规定三个钱数循环进行。
试求发放纪念章的数量。
解：设发放纪念章的数量为x，则有如下同余方程：$$\\begin{aligned} x &\\equiv 0\\pmod{5}\\\\ x &\\equiv0\\pmod{9} \\\\ x &\\equiv 0\\pmod{15} \\end{aligned}$$ 化简可得：$x\\equiv 0\\pmod{45}$，所以发放纪念章的数量应该是45.4.总结：让学生回顾今天所学知识点，并进行总结。
1 一次同余方程组同余是数论中的一个重要运算，在许多领域都有重要的应用t。
关于同余方程的解法已有一些基本的结论。
对于一次同余式的解的问题，已有下面的结果：ax≡b（modm），a≠0（modm）（1）定理1：同余式（1）有解的充分与必要条件是gcd（a，m）/b，且在有解的情况下，方程的解为：即方程的解数为gcd（a，m），其中x0是同余式（1）的一个特解。
本文基于同余的简单性质，主要讨论的是k阶一次同余方程的解法。
在我国古代的《孙子算经》里已经提出了这种形式的问题，并且得到了验证。
这就是著名的中国剩余定理。
a1x≡b1（modm1），a2x≡b2（modm2），…，akx≡bk（modmk）定理2：（中国剩余定理[1]）：设m1，m2，…，mk是k个两两互质的正整数，令m=m1m2…mk，且m=miMi，i=1，2，…，k，若a1=a2=…=ak=1，則同余式（1）的解是：X=M1'M1b1+M2'M2b2+…+Mk'Mkbk（modm）其中M1'M1=1（modmi），i=1，2，…，k。
显然，上述中国剩余定理中a1=a2=…=ak=1和m1，m2，…，mk是k个两两互质的正整数，这两个条件比较苛刻，很多情形下难以满足。
通过因子分解等手段可以将绝大部分的一次同余方程组化为满足中国剩余定理要求的形式[2]，一次同余方程组的阶数增大，导致计算的复杂程度增加。
本文主要讨论一般情形下的同余方程组解法。
2 中国剩余定理的不足之处中国剩余定理在数论中是个很重要的定理，应用于许多领域。
但是，若从解同余方程组的角度来看，也存在一些不足之处，并非首选。
文章就中国剩余定理的不足展开探讨，体现在如下3个方面。
2.1 标准化问题在前面已经提到，求解同余方程组（1），首先要求各个元素ai（mod mi）的逆元，化成满足中国剩余定理所要求的形式，即：x=a1-1b1（modm1），x=a2-1b2（modm2），…，x=ak-1bk（modmk）根据欧几里得算法或是辗转相除法得到：若gcd（ai，mi）=1，则ak-1存在。
一次同余式与孙子定理 知识扫描：1：本节将讨论一次同余方程和由此引申出的重要定理——孙子定理，首先介绍若干概念。
设整系数多项式()10,n n f x a x a x a =+++ 若有整数c ，满足()()()1212120mod ,mod .(),,f c m c x c m x c c c c c m c c ≡≡则称是满足同余方程的解，记作注：这是因为除以余的数都满足这样方程。
当且仅当都是方程的解，且与模不同余时，我们称是方程的两个不同解。
一般情况，我们说同余方程的解数，即指模m 两两不同余的解的个数。
2：最简单的同余方程是一次同余方程()()()()()()()()()()()mod ,.,/(,/,,,1,,/,,,,mod )ax b m m a a m b a m a m b a m a m a m a mp q b p q b b a m b a m a m a m a m ax b m ≡+=⇒+=≡同余方程有解的充要条件是注：必要性，若有解，则b 可用a,x 的式子表达，所以；充分性，互素则可知因为，则可知有解。
Œ()()()()()()()001,1,1mod ,1mod ,mod ,,1i i i i m a m a m x m ax m x ax a b m a a a m x ab m a m -==='≡≡'≡≡= 特别地，在时，同余方程必有解。
事实上：，遍历模的一组完系时，也遍历模的一组完系。
因此，有且仅有一个r 使得r 即同余方程至多有一个解。
进一步，一定存在使得于是即为时，同余方程的解。
j()()()()()()11122211223.1,,0mod 0mod 0mod mod mod mod i i i kk k k k k a b m a x b m a x b m a x b m x c m x c m x c m >+≡⎧⎪+≡⎪⎨⎪⎪+≡⎩≡⎧⎪≡⎪⎨⎪⎪≡⎩设是整数，是正整数，i=1,2,,k,则称下面这k 个同余式为一次同余方程式组，显然，其中若有一个同余方程无解。
一次同余式与一次同余式组的解的讨论摘 要: 这篇文章先给出有关同余式、同余式的解的概念，并在Euler 定理及孙子定理的基础上,详细地讨论了一次同余式、一次同余式组的是否有解的条件，若有解，则给出了求解方法. 一次同余式和一次同余式组的相关知识是学习数论过程中必须要掌握的知识，它在数学领域内有着及其广泛的应用。
关键词: 一次同余式; 一次同余式组;孙子定理;Euler 定理1引言南北朝时期的数学著作《孙子算经》中“物不知数”是这样的“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”解法和答案用算式表示为：702213152105223⨯+⨯+⨯-⨯=，即得到适合题意的最小正整数是23。
《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但真正从完整的计算程序和理论上解决这个问题的是南宋时期的数学家秦九韶。
秦九韶在他的《数书九章》不仅给出了一次同余式的解，而且用“大衍求一术”数学方法给出了一次同余式组的最小正整数解。
2基本定义和定理定义2.1 设1110()n n n n f x a x a x a x a --=++++ 是整系数多项式，m 是一正整数，称()0(mod )f x m ≡ (1)是模m 的同余式，若0(mod )n a m ≡/，则n 叫做同余式(1)的次数。
定义2.2 若a 是整数，且使得()0(mod )f a m ≡成立，则(mod )x a m ≡叫做同余式(1)的一个解。
即把适合(1)式且对模m 相互同余的一切数叫做同余式(1)的一个解。
定义2.3 欧拉函数()a ϕ是定义在正整数上的函数，它在正整数a 上的值等于序列0,1,2,,1a - 中与a 互质的数的个数。
定理2.1(Euler) 设1m >，(,)1a m =，则()1(mod )m a m ϕ≡。
证明 设12(),,,m r r r ϕ 是模数m 的一组简化剩余系，则由定理（若(,)1,a m x =通过m 的简化剩余系，则ax 通过模m 的简化剩余系.）可知12(),,,m ar ar ar ϕ 也是模m 的一组简化剩余系，故 12()12()()()()(mod )m m ar ar ar r r r m ϕϕ≡即 ()12()12()(mod )m m m a r r r r r r m ϕϕϕ≡ (﹡) 由于 ()i r ,1,1,2,,().m i m ϕ==故 12()(,)1.m r r r m ϕ= (﹡﹡)根据性质（若11,,(,)1,a a d b b d d m ===则11(mod ).a b m ≡） 以及 (﹡)和(﹡﹡)得 ()1(mod ).m a m ϕ≡定理2.2（孙子定理） 设12,,,k m m m 是k 个两两互素的正整数,12,(1,2,,),k i i m m m m m m M i k ===则同余式组1122(mod ),(mod ),,(mod )k k x b m x b m x b m ≡≡≡ (2)有唯一关于模m 的解111222(mod ),k k k x M M b M M b M M b m '''≡+++ (3) 其中1(mod )(1,2,,).i i i M M m i k '≡=证明 由于(,)1,i j m m i j =≠，即得(,)1i i M m =.由定理3.1知对每一i M ，有一i M '存在，使1(mod ).i i i M M m '≡由i i m m M =，知|,j i m M i j ≠. 故1(mod ),1,2,,.kjjji i i i i j M M bM M b b m i k =''≡≡=∑即(3)为(2)的解。
