下载文档原格式
初等数论同余方程组初等数论是数学中的一个分支，主要研究自然数的性质和整数的性质。
同余方程组是初等数论中的一个重要概念，它涉及到数与数之间的整除关系。
本文将介绍同余方程组的定义、性质以及解法，并通过例题来加深理解。
一、同余方程组的定义同余方程组是由若干个同余方程组成的一组方程。
同余方程的定义如下：对于整数a、b和正整数m，如果m能整除(a-b)，即(a-b)能被m整除，则称a与b对于模m同余，记为a≡b(mod m)。
这里的≡表示同余关系。
二、同余方程组的性质1. 同余关系具有自反性、对称性和传递性。
即对于任意的整数a、b和正整数m，有a≡a(mod m)，a≡b(mod m)等价于b≡a(mod m)，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。
2. 同余关系具有加法和乘法的性质。
即对于任意的整数a、b和正整数m，若a≡b(mod m)，则a+c≡b+c(mod m)，ac≡bc(mod m)。
三、同余方程组的解法1. 线性同余方程组的解法：线性同余方程组是形如ax≡b(mod m)的方程组，其中a、b为整数，m为正整数。
若a与m互质，则存在唯一的解x0，且x≡x0(mod m)。
若a与m不互质，且b可被a整除，则方程组有无穷多个解，否则无解。
2. 中国剩余定理：中国剩余定理适用于一组两两互质的模数的同余方程组。
设m1、m2、...、mn为两两互质的正整数，a1、a2、...、an为整数，则同余方程组：x≡a1(mod m1)x≡a2(mod m2)...x≡an(mod mn)有唯一的解x，且0≤x<m1m2...mn。
四、例题解析1. 解线性同余方程组：求解方程组2x≡3(mod 5)和3x≡4(mod 7)。
首先，对于第一个方程，由于2与5互质，所以存在唯一解x0。
根据扩展欧几里得算法，我们可以求出x0=4。
然后，将x0代入第二个方程，得到3*4≡4(mod 7)，即12≡4(mod 7)。
学院学术论文题目: 同余的概念及其基本性质学号：学校：专业：班级：姓名：指导老师：时间：摘要：初等数论是研究数的规律，特别是整数性质的数学分支。
它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。
同余概念的产生可以说大大丰富了数学的内容。
同余是数论中的一个基本概念，同余的应用，一：检查因数的一些方法；二：弃九法。
在本专题的学习中，培养我分析推理解决问题的能力，理解问题的实质。
关键字：同余整数算术Summary：The number of elementary number theory is to study the law, in particularinteger nature of the branch of mathematics. It arithmetic method as the main research methods in their daily lives, we are often not to pay attention to some integer, but these numbers with a fixed a number of removal from the remainder. I created the concept of the same can be said to have greatly enriched the content of mathematics. Number theory congruence is a basic concept of the application with more than one: Check factor of some of the ways; 2: abandoned nine law. In the topic of study, training my analysis reasoning ability to solve problems, understand the essence of the problem.Keyword ：Congruence Integer Arithmetic引言数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。
第三讲：初等数论3——同余的性质和应用三、巩固练习1. 今天是星期三，到第1000天是星期几？解：从今天到第1000天相隔999天，1000-1≡5(mod 7)，3+5-7=1，是星期一.2. 若1059，1417，2313分别被自然数x除时，所得余数都是y，则x-y= ．解：∵1059≡y(mod x) ，1417≡y(mod x) ， 2313≡y(mod x)，∴1417-1059=358≡0(mod x)，2313-1417=896≡0(mod x)， 2313-1059=1254≡0(mod x)又（358，896，1254）的最大公约数为2，则x=2， y=1，x-y=1．3. 若正整数a和1995对于模6同余，则a的值可以是（）A. 25B. 26C. 27D. 28解：1995除以6的余数是3，a≡1995 (mod 6)，a除以6的余数也是3，只有a=27，选C.4. 一个两位数被7除余1，它的反序数被7除也余1，那么这样的两位数共有（）A. 2个B. 3个C. 4个D. 5个解：列出满足条件的所有两位数：15，22，29，36，43，50，57，64，71，78，85，92，99 两位数据反序数也满足条件的有：22，29，92，99，选C.5. 设n为自然数，则32n+8被8除的余数是_________.解：由32n+8=9n+8，知32n+8≡1n+0(mod 8)≡1(mod 8) ，故32n+8被8除余1.6. 黑板上写着13个数：1908，1918，1928，1938，1948，1958，1968，1978，1988，1998，2008，2018，2028．小明第一次擦掉其中的一个数，第二次擦掉剩下数中的两个数，第三次擦掉剩下数中的三个数，第四次擦掉剩下数中的四个数，他想使得每次擦掉数后剩下的所有数之和为13的倍数，小明的意图能否达到？如果可以，给出一种可行的方法，不能请说明理由．答案：可以：依次擦掉（2028）；（1958，1968）；（1908，1938，1978）；（1918，1928，1998，2008）。
同余式作者：张新春来源：《湖南教育·C版》2017年第11期同余是初等数论的重要组成部分。
同余的概念可以说来源于现实。
现实生活中有很多周期性变化的事物。
比如星期，以7天为一个周期，于是考虑10天后是星期几，只需要考虑3天后是星期几。
再如生肖纪年，以12年为一个周期。
2017年是鸡年，再过12年还是鸡年，而再过30年是什么年，就只要看过6年是什么年就行了。
这里10和3对于7，30和6对于12，都具有某种相同的关系。
把这种关系抽象出来，就是同余的概念。
同余式的定义给定一个正整数m，如果整数a和b被m除所得的余数相同，则称a和b对于模m同余，记作a≡b（modm）。
这里的mod是英文modulus的简写，读作模，a≡b（modm）可读作a和b对于模m同余。
整数a和b被m除所得的余数相同，就意味着a和b的差能被m整除。
于是a≡b （modm）就意味着有整数k，使得a-b=km。
这可以理解为同余的另一种等价的定义方式。
在以后证明同余的有关性质时，用这个定义将更方便。
表示同余的符号“≡”由“数学王子”高斯发明。
1801年，年仅24岁的高斯写就著名的数论专著《算术研究》。
在此书中，高斯用这个符号表示同余。
他在书中写道：“今后我将用符号≡表示两个数的同余式，模则放在括弧内，如-16≡9（mod5）；-7≡15（mod11）。
”（徐品方，张红.数学符号史[M].第338页.科学出版社，2006.9）同余式的基本性质同余式具备如下三条基本性质。
1.反身性，a≡a（modm）；2.对称性，若a≡b（modm），则b≡a（modm）；3.传递性，若a≡b（modm），b≡c（modm），则a≡c（modm）。
反身性与对称性是非常明显的，我们只证明传递性。
事实上，由a≡b（modm）知a-b=km，由b≡c（modm）知b-c=lm。
上述两式相加，有a-c=（k+l）m。
这就意味着a≡c（modm）。
传递性得证。
同余方程1997年第3期高等函授(自然科学版)同余彭敦刚(湖北大学)同余方程是初等数论中一个重要的问题.其内容包括一次同余方程(组),高次同余方程,二次同余方程等.如去掌握这些内容呢?下面就其特征分述如下,供复习时参考.l一次同余方程(组)在这个问题中,主要讨论的是含有一个未知数的一次同余方程和含有一个未知数的一次同余方程组.1.1一次同余方程如果口,b都是整数,而T/l是一个正整数,当口≠0(modm)时,我们把口+6三0(modm)(1)叫做模.的一次同余方程.对这一类方程的求解,主要应该掌握:设有方程(1),当(口.)一1时,则方程(1)有唯一的解;--6t~(一.b(modm)(2)当(口,)=>1时,则方程(1)有解的充分和必要条件是}b,这时方程(1)有d个解是三+.(modm),t=O,1,…,一1(3)这里x~a(modm)是把第二种情形化为第一种情形时,所得到的唯一解.要注意的是:对于第一种情形,在实际求解时,不常用公式,因为用公式一般比较麻烦,应该灵活地运用已有的知识去寻找新的简便的求解方法.后面将举例说明.对于第方程李德水(武汉电视大学)二种情形是把它化成第一种情形求解来处理的,求出唯一解后,再代入公式(3)求得它的d个解.对于方程(1)除了上述方法求解外.主要的还有如下两种解法.第一种解法因(口,z)一1,由(n,)一1的充分必要条件:存在s,t,使口s+bt一1知. 必有二数,t,使-口s+mt1即口s三I(modm)故由asx~bs(modm),得三(modm)为同余方程(1)的解.第二种解法先把方程(1)写成;一b(mod0)一——L,n的形式,然后用与z互质的整数陆续乘以右端的分子和分母,目的在于把分母的绝对值变小,直到变成1为止.下面举例说明上述三种解法的应用.例1解方程286x~121(mod341).解法1因(286,341)一11,11I121,故26三11(mod31)(*)因为口一26,6—11,(31)一30故方程(*)的解是;一n…一'6三一261.?11三4(mod31)将三4(mod31)代入公式(3),因此,原方程的解是z_二4.35.66.97.】28,】59.于是z[N(E+)]≥nl[EN+]:z[En]>2()>2()收稿日期:1997一O4—29这与前面",[n(E+jt)]<1",(』)产生矛盾故命题得证.原方程有解,并且有11个解. 将原方程写成1997年第3期高等函授(自然科学版)25 190,221,252,283,314(mod341)解法2由(286,341)一ll得到(26,31)一1,这样就存在两个整数,t,使26s+3It一1由观察方法可知:26?6+31?(一5):1即26?6兰1(mod31)又由同余性质,(*)式可写成26?6x=11?6(mod31)即x-~-66=4(mod31)将兰4(mod31)代入公式(3)即可得到原方程的解.2-三4,35,66,97,128,159,190,221,252,283,314(rood341)解法3把(*)式写成兰11三兰一4三4(m.d31)1561—26……将兰4(rood31)代入公式(3)即可得到原方程的解:兰4,35,66,97,128,1S9,190,221,252,283,314(mod341)在此应该注意的是:以上3种解法各有各的优点.在模很大时,第1种解法较好;而当模不太大时,第2种解法比较简捷;若模较小时.第3种解法较方便.总之,在解题时,要根据具体情况选择其方法.1.2一次同余方法组在这里所讨论的一元一次同余方程组,主要的是形如f~2.61.2?,)j.2?;6(modm.)的同余方程组.在我国古代的孙子算经》里就提出了这种形式的问题,并且很好地解决了.这个问题的解法主要依靠下面的定理.定理设11ll,11l?,…川z女是是个丽两互质的正整数,z一Ⅲ2…11l女.11l一111M,i一1, 2,…,正,则同余方程组(4)对于模z一z.?兰-+.+..?+b(modz)(5)这里,三1(m.d).x=l(mod7);再由兰1(modz)可以求得261997年第3期高等函授(自然科学版)高次同余方程分两种情形,一是质数模的高次同余方程,另一是合数模的高次同余方程,而合数模高次同余方程是把它化成质数模高次同余方程进行处理的(这里应掌握转化方法).对这两种类型的高次同余方程应掌握:1)如何对()进行化简;2)求解的基本方法:将P的完全剩余系10,±1,…,±÷(p一1)中的每一个数一一代厶人进行验证的方程;3)在合数模的高次同余方程中有一种特殊的质数幂模的高次同余方程,这种类型的方程在求解时应严格按照求解步骤进行.例3解同余方程6x.+27x+17x+20三0(mod30)解由30—5×6,所以同余方程与同余方程组f6+27x+17+20三0(mod5)(6)l6+27x+17+20三0(rood6)(7)等价.直接验算得:(6)式有3个解:三0,1,2(mod5);(7)式有2个解:三一1,2(mod6).故原方程有3×2:6个解.设三b(moA5),三62(mod6),其中bl一0,1,2,b2一一1,2.由孙子定理可得原方程的解丁三6bl+25b:(mod30)以b一0,1,2,b:一一1,2代入上式,即可得原方程的6个解是-『三三三2,5,11,17,20,26(mod30)当然也可把30—2×3×5,得到三个方程组成的方程组与原方程等价,同样得到原方程的6个解,请读者自行完成.3二次同余方程二次同余方程的求解问题是二次同余方程与平方剩余的一个中心问题.这个问题中也是分质数模二次同余方程和合数模二次同方程两种情形来讨论的.3.1奇质数模的二次同余方程的求解设.三口(modp),户,P是奇质数(8)当(詈)一1时,说明n是P的平方剩余,方程(8)有解.这时方程(8)的解分下面4种情形:p=l(mod8),pz3(mod8)p=5(mod8),p=7(mod8)当p=3或户三7(mod8)时,方程(8)有解,即三±口寺'p(mod)当p=5(mod8)时,若口}(p-1)三1(modp),则方程(8)的解是三±口音'p.(mod)若口}(p--1)三一1(modp),则方程(8)的解三±2}(p—1).口告(p+3(mod3)例4求同余方程三19(mod31)的解.解因为(19)一1,所以同余方程有解.又因为31=8×3+7,所以三±19}.件"三三三±19三±19(mod31)故原同余方程的解是三士19(mod31)例5求方程3x.+7x一6三0(modl3)的解.解因为(3,13)一1,所以3+13N一1.因此,3三1(modl3).由M三9(mod13), 以9乘原方程两边得.r.+63.r一54三0(mod13)上式中63不是偶数.因此上式可以写成.7/-?+(63+13)一54三0(mod13)即3/0+24:r一2三0(mos13)配方得(j-+12)三12+2-----1463(mod13) 令—J'+12即y三3(rood13)又()一1,所以上面方程有解.又13—8X1+5,所以3{'.一三3三1(mod13),上面方程1997年第3期高等函授(自然科学版)27的解为兰_--4-3言'...兰±3.三±9(modl3)将代入—+12,即得z=---5,10(modl3)故原方程的解为z三5,10(mod13)在这里要说明的是,在求z.三口(modp)方程解时,首先要用()符号进行判断,看该p方程是否有解;其次如果该方程有解,再用P 三3,户兰5,p~7(modp)判断,才能确定该方程其解的形式;再次,如果二次同余方程是以口.+bx+c三0(modp)形式出现的,要把它化成:兰(modp)形式,再按前面二步进行求解.上面我们就户三3,户兰5,户三7(modp) 三种情形进行了介绍,但对P三1(modp)情形未进行讨论.这里要说明的是这种情形要比前面三种情形要复杂得多,没有一般结论, 请在复习时按书上的要求进行复习.3.2合数模二次同余方程在这里要明确合数模二次同余方程z:三Ⅱ(modm),(口删)一1,竹l为合数(9有解的条件及解的个数.对于这类方程我们是先把写标准分解形式,即17'1—2opi'…声.由定理:若一I'H!…I'H,且,…,17'1女是k个两两互质的jE整数,则同余方程厂()~O(modm)与方程组f(x)~O(modm,)一1,2,…,是等价.有解的必要和充分条件是z.三口(mod2.)z.三口(modt),一1,2,…,k(10)有解,并且在有解的情况下,(9)的解数是(1O)的解数的积.在这里主要是讨论形如z.三口(modp.),a>0且(口,户)一1(11)的方程,在求解方程(11)时,所用的方法是质数幂模的高次同余方程求解方法.例6解方程z.~7(mod27).解因7三7r兰1(rood3),即.三1(mod3)有解为三1(mod3).再从(1+3t1).三7(rood3.)得6tI三6 (mod3.),因此t三1(mod3).于是1+3t,三4(mod3:)是三7(mod3:)的解.又从(4+32t2)三7 (mod30)得8t2三一1(mod3)即可得t2E1(mod3),所以z三4+3zt2三13(mod3)是所给方程的一个解.于是所求方程的解是z三±13(mod27)至于同余方程z0三口(moda),口>0且(2,")=1的求解,按照书上要求即可.(上接第17页)有nt肌B.E一exp[Sc肿B.E/k3(31)将(29)式的代入(31)式,并令s一Nk(1nZ一』9茄nzI)(32)(这是未考虑波函数的对称性时算得的熵,即玻耳兹曼系统的熵)便可得到c¨B,E一exp[S【肿B.E,/忌]一【,,,'^exp[丢(+是ln1j一斫es'Ik—(33)可见(3)式中的因子1/Ⅳ!也来源于波函数的交换对称性.参考文献l曾谨言.量子力学(上册).北京:科学出版社1981:189—2012R.K.帕斯里亚着.湛垦华,方锦清译.统计力学(上册),北京:商等教育出版社1985:1743Kerr:mHuang,StatisticalAlechanics?Ne'u~Y ork:Jobnuih:3rSons.Inc.1963:213。
