下载文档原格式
详析一次同余式求解定理的证明教学方法详析一次同余式求解定理的证明一[摘要]一次同余式求解定理的证明,在各版本的数论课本中均有介绍,但跳跃性都比较大,使读者在学习过程中会有很多疑问,本文就该定理给出详细的思路分析与证明过程. [关键词]一次同余式证明概念,定理介绍同余方程定义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)的解。
学院学术论文一次同余式组的解法A congruence of the solution姓名所在学院专业班级学号指导教师日期摘要:研究了有关同余式组的解法,特别是孙子定理的应用,当模不两两互质时,就不能用孙子定理来解了,那该怎么办呢?我们将在实例的求解中来揭密.[Summary] Has studied the related congruence group's solution, specially Residue theorem application, when the mold 22 are not coprime, could not use the Residue theorem to solve, how should that manage? We will reveal in the example solution.关键字:一次同余式组 模 孙子定理[Key words] A congruence group Mold Residue theorem 正文：引理 1. （孙子定理）设1m ，2m ………. km 是k 个两两互质的正数，m=12......k m m m , m=i i m M , i=1,2,…,k ,则同余式组x ≡1b (mod 1m ),x ≡2b (mod 2m )，…，x ≡k b (mod k m )的解为：x ≡`111M M b +`222M M b +…+`k k k M M b (modm ）,……(2)，其中`i M M ≡1（mod i m ）,i=1,2,…,k.证明：由（i m ，j m ）=1，i ≠j 即得（i M ，i m ）=1，故由§1定理即知对每一i M ，有一`i M 存在，使得`i i M M ≡1（mod i m ）.另一方面m=i m i M ,因此j m |i M ，i ≠j ，故`1k j j j j MM b =∑≡`i i i M M b ≡i b （mod i m ）即为（1）的解。
所谓“一次同余式”问题，最早可见《孙子算经》卷下第26题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问数几何？”用现代数学语言表示，就是求解一次同余式组：N≡R1（mod3）≡R2（mod5）≡R3（mod7）其解可表示为：N＝70 R1＋21 R2＋15 R3－105P这里P为整数，在上述问题中，R1＝R3＝2，R2＝3，取P＝2，得到答案：N＝23。
在明朝程大位的数学著作《算法统宗》中，上述题解被写成一首在数学史上流传颇广的歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知。
不能小看这道题目（在数字很小且只有三组的情况下，凑数字也能求出其解），它背后的学问还是很大的。
在欧洲，大约在公元10世纪时开始出现讨论一次同余式问题的萌芽，而世界科学史上一连串辉煌的名字都曾和这个问题联系在一起：例如阿尔哈桑（Ibn al Haithan）、斐波那契（Fibonacci）、欧拉（L. Euler）、拉格朗日（J. Lagrange）、高斯（Gauss）……。
后来来华的传教士伟烈亚力（Alexander Wylie）将《孙子算经》卷下第26题介绍到了欧洲，1874年L. Methiesen发表文章，指出《孙子算经》中的解法与高斯定理相合，于是西方人将其定名为“中国剩余定理”。
秦九韶在《数书九章》中明确地系统地叙述了求解一次同余组的一般计算步骤。
秦的方法，正是前述的剩余定理。
我们知道，剩余定理把一般的一的一组数Ki的选定。
秦九韶给这些数起名叫“乘率”，并且在《数书九章》卷一“大衍总术”中详载了计算乘率的方法——“大衍求一术”。
为了介绍“大衍求一术”，我们以任一乘率ki的计算作例。
如果Gi≡gi（modai），于是kiGi≡Kigi（modai），但是因为kiGi≡1（modai），所以问题归结为求ki使适合kigi≡1（modai）。
秦九韶把ai叫“定数”，gi叫“奇数”，他的“大衍求一术”，用现代语言解释，实际就是把奇数gi和定数ai辗转相除，相继得商数q1、q2、……qn和余数r1、r2、……rn，在辗转相除的时候，随即算出下面右列的c值：1，20定ai271，gi1，20c1=q1，r21，7(q1)(q2)c2=c1q2+1，r23，6c1，r11，7cn-2，rn-23，6cn-1=cn-2qn-1+cn-3，rn-14，1(qn-1)(qn)cn=cn-1qn+cn-2，123，1cn-1，rn-14，1秦九韶指出，当rn＝1而n是偶数的时候，最后得到的cn就是所求乘率ki。
公式化解决一次同余方程和一次不定方程的探索摘要】运用余数方程周期表的自变律和周变性质，对首项余数进行模运算再转化。
简明扼要地推算任意两个不等的正整数的最大公约数和余数方程的整数解。
运算过程紧凑严密，环环相扣，一气呵成。
比较传统的方法，显得更为简明，快速直接，不拖泥带水，容易记忆，使用方便，是一次同余方程和二元一次不定方程解法公式化的一次有效探索。
【关键词】余数方程；周期表；自变律；公式化【中图分类号】G633.6【文献标识码】A【文章编号】1009-9646（2009）03-0010-03一次同余方程ax≡ c(modb)（a>b>0的整数，c为整数）或二元一次不定方程的解法在初等数论中多采用辗转相除得到a、b的最大公约数后再反向代入最大公约数的表达式[1、2]，或者将不定方程（或余数方程）未知数的系数（或模），用辗转相除法转化为一个比一个绝对值更小的不定方程（或余数方程），再一步步反向推导回原方程获得结果[3]。
本工作用余数周期表原理[4]，推导的余数自变定理（1）、（2）用模运算再转化的方法，将余数方程未知系数转化到绝对值是a、b最大公约数的子余数，组建余数子方程来讨论，因为这个子余数是周期表中绝对值最小余数（0除外）由其组建的余数子方程的问题会得到充分的、自然的暴露迎刃而解。
又因为余数子方程与它的母方程有着十分密切的关系，子方程有无整数解代表了母方程有无整数解；子方程整数解的解数代表了母方程整数解的解数；子方程中的子余数在周期表中的项数与余数子方程整数解（px）的乘积代表了母方程的整数解。
解决了余数子方程的问题，实际上就解决了母方程的全部问题。
这样，自变余数模运算再转化，把求解一次同余方程和二元一次不定方程的问题，简化到象解普通一元代数方程那样简单、快捷、干净利落，走向了公式化，条理化的道路。
为一次同余方程和二元一次不定方程的求解，提出了一套全新的解决解决模式。
1. 余数自变规律的有关定义、概念、名词、术语的解释定义1余数的自变：余数方程ax≡ c(modb)周期表中任一项余数cn若在xn项，则余数cn每过xn项，余数递增cn。
一元一次同余式的解法
李淑华
【期刊名称】《河北民族师范学院学报》
【年(卷),期】2004(024)002
【摘要】一元一次同余式的解法,是学生不易掌握的问题,当(a,m)=1时,若a,b＜m,(a,b)=1,且模数较大,可取余;若a,b＜m,(a,b)=1,且模数较小,用欧拉定理;若(a,b)=1,且a,b中至少有一个数大于m,利用同余知识,将a,b化小;若(a,b)≠1,约去两端的公因数;当(a,m)=d＞1时,用d去除同余式,再按(a,m)=1的情况去解.【总页数】1页(P10-10)
【作者】李淑华
【作者单位】河北大学,数学与计算机学院硕研班,河北,保定,071000
【正文语种】中文
【中图分类】O122.2
【相关文献】
1.一次同余式的解法探讨 [J], 刘耀斌
2.一元二次同余式解法举例 [J], 张世红
3.一元二次同余式解法举例 [J], 张世红;
4.主理想整环上的一元一次同余式组 [J], 吴培炯
5.主理想整环上的一元一次同余式组 [J], 吴培炯
因版权原因，仅展示原文概要，查看原文内容请购买。
