下载文档原格式
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 2009年第3期 牡丹江教育学院学报 No 13,2009(总第115期) J OU RNAL OF MUDANJ IAN G COLL EGE OF EDUCA TION Serial No 1115[收稿日期]2008-12-22[作者简介]原新生(1967-),男,河南林州人,安阳师范学院副教授,主要从事初等数论、高等数学的教学与研究.。
一次同余方程的几种解法原 新 生(安阳师范学院,河南安阳455002) [摘 要] 介绍一次同余方程的几种解法,并比较它们的优劣,探讨不同情况下所应采用的不同方法,对解一次同余方程具有一定的指导作用。
[关键词] 一次同余方程;解法;完全剩余系[中图分类号]O151 [文献标识码]A [文章编号]1009-2323(2009)03-0115-01 定义1:设a ,b 为整数,m 是一个正整数且a ≠0(modm ),则称ax ≡b (mod m )为模m 的一次同余方程。
定义2:若x 0是使ax ≡b (mod m )成立的一个整数,则x ≡x 0(mod m )称为一次同余方程ax ≡b (mod m )的一个解。
定理:一次同余方程ax ≡b (mod m ),a ≠0(mod m )有解的充要条件(a ,m )|b,且有解时解数为(a ,m ).一次同余方程的理论各初等数论教材都作了详细的论述(见[1]、[2]、[3]),但对它的具体解法介绍的较少。
笔者在初等数论教学实践中,针对该方程总结了几种解法,并通过各种解法优劣的比较,探讨了在不同情况下所应采用的不同方法,这对学生学习初等数论,特别是解一次同余方程具有一定的指导作用。
方法一:验根法由定义2可以看出,求一次同余方程ax ≡b (mod m )有几个解,有哪些解,只需取模m 的一个完全剩余系(如0,1,2,…,m -1)中的每一个数,将其代入同余方程中逐一验证,即可求出其全部解。
初等数论学习总结本课程只介绍初等数论的的基本内容。
由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的．一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的．正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。
最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。
数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中着名的“哥德巴赫猜想”和费马大定理的阅读材料。
初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。
第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++ 2211 勾股数 费尔马大定理。
习题要求29p ：1，2，4；31p ：2，3。
第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。
第四章：同余式（方程）（4学时）自学12学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。
浅谈初等数论中同余式的解法
初等数论是数学的一个分支，主要探讨整数、有理数和代数式等基础概念。
“同余”是初等
数论中概念的一个重要部分，它引用数学定义可以写为：若两个有理数或者有理函数在一
个事件上有相同的值，则它们称为“同余”。
也就是说，两个有理数或者有理函数的值不同，但它们的值是相等的。
同余的解法首先应该把同余方程写成有理函数的形式，然后进行求解。
一般可以使用图像法、合并法或者二分法来求解。
图形法是一种直观清晰的求解方法，它通过在坐标系中绘制图像来求解同余方程，从而得到所求解的值。
这是最简单也是最容
易理解的求解方法。
合并法是一种基于数学运算技巧的求解方法。
它通过合并两个同余方程来求解同余方程，得到所求的值。
二分法是运用有理数的属性来求解的方法，用二分的方法对有理数的值进行查找，来获得有理数的值。
以上就是同余的几种常用方法，虽然每种方法都有其优势和缺点，但它们都是多元素的有理函数。
使用正确的方法，可以对同余
方程进行快速准确的求解，以解决初等数论中的多元素有理函数问题。
初等数论同余方程组初等数论是数学中的一个分支，主要研究自然数的性质和整数的性质。
同余方程组是初等数论中的一个重要概念，它涉及到数与数之间的整除关系。
本文将介绍同余方程组的定义、性质以及解法，并通过例题来加深理解。
一、同余方程组的定义同余方程组是由若干个同余方程组成的一组方程。
同余方程的定义如下：对于整数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)。
初等数论的性质与定理总结初等数论是数论中的一个基础分支，研究整数的性质和整数运算规律。
本文将总结初等数论中的一些重要性质与定理。
一、整数的整除性质1. 整数的除法基本性质：对于任意整数a、b和非零整数c，存在唯一的整数q使得a = bq + c。
2. 整除关系的传递性：如果a能整除b，且b能整除c，则a能整除c。
3. 整除关系的辗转相除法：对于任意整数a和非零整数b，存在唯一的整数q和r使得a = bq + r（其中0 ≤ r < |b|）。
二、质数与合数1. 质数的定义：质数是指大于1且只能被1和自身整除的整数。
例如，2、3、5、7等都是质数。
2. 质因数分解定理：每个大于1的整数都可以唯一地表示为若干个质数的乘积。
3. 最大公约数与最小公倍数的性质：对于任意整数a和b，记a和b 的最大公约数为gcd(a, b)，最小公倍数为lcm(a, b)，则有以下性质： - gcd(a, b) = gcd(b, a)- gcd(a, 0) = |a|- lcm(a, b) = |ab| / gcd(a, b)三、模运算与同余1. 模运算的基本性质：对于任意整数a、b和正整数n，有以下性质：- (a + b) mod n = (a mod n + b mod n) mod n- (a - b) mod n = (a mod n - b mod n) mod n- (a * b) mod n = (a mod n * b mod n) mod n2. 同余关系的性质：对于任意整数a、b和正整数n，如果a与b模n同余（记作a ≡ b (mod n)），则有以下性质：- a + c ≡ b + c (mod n)- ac ≡ bc (mod n)- 如果a ≡ b (mod n)，则a^k ≡ b^k (mod n)对于任意正整数k四、费马小定理与欧拉定理1. 费马小定理：如果p是质数，a是任意正整数且p不整除a，则有a^(p-1) ≡ 1 (mod p)。
本科毕业论文题目：同余方程的解法学生姓名：学号：专业：数学与应用数学班级:指导教师：二〇一年四月摘要：本文论述了同余方程的基本概念及同余方程的一些基本性质与解法，主要对一次同余方程的解法进行了探讨，特别是对一次同余方程的欧拉定理算法，欧几里德算法等七种解法进行了比较与分析，并介绍了同余方程组、孙子定理、素数模的同余方程，模p 的同余方程的解法。
关键词：同余同余方程孙子定理Abstract：This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the congruence equation,mod p congruence equation solution,congruence equation of primes mode solution,etc.Key words:Congruence Congruence equation Remainder Theorem目录引言 (1)1.同余与同余方程的基本性质 (2)1.1 同余的概念与基本性质 (2)1.2同余方程的概念与性质 (3)2.一次同余方程的解法 (4)2.1 ()a=的情况 (4), m 12.2 ()=≠的情况 (7),1a m d3.同余方程组的解法 (8)3.1简单同余方程组的解法 (8)3.2 孙子定理 (9)4.高次同余方程的的解法 (11)4.1素数模的同余方程 (11)4.2模pα的同余方程 (12)总结： (17)参考文献 (18)致谢： (19)引言对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。
同余方程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。
中国剩余定理求解同余方程组同余方程组是初等数论中的一个重要知识点，解同余方程组需要用到中国剩余定理。
中国剩余定理是数论中的一个重要定理，用于解决同余方程组问题，这里我们简要介绍一下中国剩余定理和它在求解同余方程组中的应用。
中国剩余定理是一种求解一类特殊的同余方程组的方法。
它有如下形式：设n1,n2,…,nk为两两互质的正整数，a1,a2,…,ak任意整数，则同余方程组：x ≡ a1 (mod n1)x ≡ a2 (mod n2)......x ≡ ak (mod nk)有唯一解 x = X(mod N),其中 X是满足上述同余方程组的最小正整数解，N = n1∗n2∗…∗nk。
步骤如下：第一步：对于给定的同余方程组，判断其中的n1,n2,…,nk是否两两互质，如果不是，则调整使其中任意两个相邻的ni和ni+1满足条件gcd(ni, ni+1) = 1。
第二步：根据题目中给出的同余方程组，分别解出下列方程的x的值：x ≡ a1 (mod n1)x ≡ a2 (mod n2)……最后所需求解的方程组形如下式：x ≡ X (mod N)第三步：将上一步所得的解x代入此方程中，得到它的最小非负整数解X，这就是所求出最终方程组的解。
下面用一个具体的例子来演示如何用中国剩余定理求出同余方程组的解：问题：求解下列同余方程组的解。
x ≡ 2 (mod 3)x ≡ 3 (mod 4)x ≡ 2 (mod 5)解：第一步：我们注意到其中任意两个相邻的n(即3,4,5)都不是互质的，所以需要调整题目给出的方程组，从而使之满足两两互质的条件，我们选择将3和4调整成互质的。
x ≡ 2 (mod 3)x ≡ 3 (mod 2∗2)x ≡ 2 (mod 5)我们可以将2∗2转化为4，也可以将2∗2转化为2+2，即x ≡ 2 (mod 3)x ≡ 3 (mod 4)x ≡ 2 (mod 5)第二步：我们对于方程组中的每个方程分别求出x的值，如下：x ≡ 2 (mod 3) ，由x = 3k + 2，所以最终得到 x1 = 2。
初等数论_第五章__同余方程第五章同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。
在本章中，总假定m是正整数。
定义1设f(x) = a n x n+ +a1x+a0是整系数多项式，称f(x) ≡ 0 (mod m) (1) 是关于未知数x的模m的同余方程，简称为模m的同余方程。
若a n≡/0 (mod m)，则称为n次同余方程。
定义2设x0是整数，当x = x0时式(1)成立，则称x0是同余方程(1)的解。
凡对于模m同余的解，被视为同一个解。
同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。
由定义2，同余方程(1)的解数不超过m。
定理1下面的结论成立：(ⅰ) 设b(x)是整系数多项式，则同余方程(1)与f(x) +b(x) ≡b(x) (mod m)等价；(ⅱ) 设b是整数，(b, m) = 1，则同余方程(1)与bf(x) ≡ 0 (mod m)等价；(ⅲ) 设m是素数，f(x) = g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x) ≡ 0 (mod m) 或h(x) ≡ 0 (mod m)107108 的解。
证明留做习题。
下面，我们来研究一次同余方程的解。
定理2 设a ，b 是整数，a ≡/0 (mod m )。
则同余方程ax ≡ b (mod m ) (2)有解的充要条件是(a , m )∣b 。
若有解，则恰有d = (a , m )个解。
证明显然，同余方程(2)等价于不定方程ax + my = b ， (3)因此，第一个结论可由第四章第一节定理1得出。
若同余方程(2)有解x 0，则存在y 0，使得x 0与y 0是方程(3)的解，此时，方程(3)的全部解是-=+=t m a a y y t m a m x x ),(),(00，t ∈Z 。
初等数论教材引言初等数论是数学的一个分支，研究的是正整数的性质和关系。
虽然初等数论的研究对象看似简单，但它在数学发展中扮演着重要的角色。
初等数论不仅对数学本身具有重要意义，而且在密码学、编码理论、密码破解等领域也有广泛的应用。
本教材将介绍初等数论的核心概念和基本原理，以帮助读者建立对初等数论的基础知识和理解。
一、数的整除性1.1 整除和倍数在初等数论中，整除是一个重要的概念。
对于整数a和b，我们称a能整除b，记作a|a，当且仅当存在整数k，使得b = ak。
例如，12能整除36，记作12|36，因为36 = 12 * 3。
我们也可以说36是12的倍数。
1.2 素数和合数素数是指只能被1和自身整除的正整数，大于1的整数中，只有1和本身两个正整数可以整除它的数。
合数是指有除了1和本身之外的其他因子的正整数。
素数和合数是初等数论中的重要概念，我们将在后续章节中深入讨论它们的性质和应用。
二、最大公因数和最小公倍数2.1 最大公因数最大公因数（Greatest Common Divisor，简称GCD）是指能够同时整除两个或多个整数的最大正整数。
最大公因数有很多计算方法，常见的有质因数分解法、辗转相除法等。
这些方法将在后续章节中详细介绍。
2.2 最小公倍数最小公倍数（Least Common Multiple，简称LCM）是指能够被两个或多个整数整除的最小正整数。
最小公倍数的计算方法是基于最大公因数的，我们将在后续章节中给出详细的算法。
三、模运算与同余3.1 模运算模运算是初等数论中一个重要的概念，它描述了两个数之间的相对关系。
对于整数a和正整数m，a对m取模运算的结果记作$a \\equiv b \\pmod{m}$，读作“a同余于b模m”。
模运算有一些基本性质和规则，比如加法、减法、乘法和幂运算等。
我们将在本章节介绍这些性质以及它们的应用。
3.2 同余同余是模运算的一个重要应用。
当两个数a和b对模m取模运算的结果相同时，我们称a与b同余模m，记作$a\\equiv b \\pmod{m}$。
一次同余方程的解法及应用初等数论是数学基础理论的一个分支，它主要研究的是整数的性质和方程的整数解。
由于初等数论中的问题简明易懂，所以近代数学中许多重要的思想、方法和技巧都是从对整数性质的深入研究而丰富并发展起来的。
在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。
例如我们问现在几点钟，就是用24去除某一个总的时数所得的余数,同是几点钟或同为星期几。
常常在生活中有同样的意义，这样，就在数学中产生了同余的概念。
这个概念的产生可以说大大丰富了数学的内容。
在代数里面一个主要的问题就是解代数方程，而同余方程是同余理论的核心内容。
在这里我们所要研究的就是关于同余方程的一些基本知识、概念、术语等，以及对于一次同余方程，一次同余方程组等等的求解问题。
一、同余方程设整系数多项式f（x）=anxn+…+a1x+a0（1）我们可讨论是否有整数值x满足同余式f（x）≡0（mod m）（2）我们要求解的这个同余式（2）称为是模的同余方程。
若整数c满足f（c）≡0（mod m），则称c是同余方程（2）的解，我们把这个解记为x≡c（mod m）。
这实际上是把同余类cmodm看作是满足同余方程（2）的一个解。
当c1、c2均为同余方程（2）的解，且对模不同余时，才把它们看作是不同解，我们把所有对模m 两两不同余的（2）的解的个数（即满足“2”的模m的同余类的个数）称为是同余方程（2）的解数。
因此，我们只要在模m的一组完全剩余系中来解模m的同余方程。
显然，模m的同余方程的解数至多为。
例1: 求同余方程4x2+27x-12≡0（mod 15）的解。
解：取模15的绝对最小完全剩余系：-7，-6，…，-1，0，1，2，…，7。
直接计算知x=-6，3是解。
所以，这个同余方程的解是x≡-6，3（mod 15）。
例2: 求同余方程4x2+27x-9≡0（mod 15）。
直接计算知这个方程无解。
当f（x）的系数都是模m的倍数时，显见，任意的整数值x都是同余方程（2）的解，这样的同余方程（2）的解数为m，但并不是同余方程（2）的解数为m的必要条件，这可由下面的例子看出。
《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。
有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。
这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。
老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。
知识点总结第一章 整数的可除性1. 定义：设是给定的数，，若存在整数，使得则称整除，记作，并称是的一个约数，称是的一个倍数，如果不存在上述，则称不能整除 2性质：(1)若且，则(传递性质)；(2)若且，则即为某一整数倍数的整数之集关于加、减运算封闭。
若反复运用这一性质，易知及，则对于任意的整数有。
更一般，若都是的倍数，则。
或着，则其中；(3)若，则或者，或者，因此若且，则； (4)互质，若，则；(5)是质数，若，则能整除中的某一个；特别地，若b a ,0≠bc bc a =b a a b |b a a b c b a c b |a c |a b |a b |c b |)(|c a b ±a b |c b |v u ,)(|cv au b ±n a a a ,,,21 b )(|21n a a a b +++ i b a |∑=ni ii b c a 1|n i Z c i ,,2,1, =∈a b |0=a ||||b a ≥a b |b a |b a ±=b a ,c b c a |,|c ab |p n a a a p 21|p n a a a ,,,21是质数，若，则；(6)(带余数除法)设为整数，，则存在整数和，使得，其中，并且和由上述条件唯一确定；整数被称为被除得的(不完全)商，数称为被除得的余数。
第五章同余方程本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节同余方程的基本概念本节要介绍同余方程的基本概念及一次同余方程。
在本章中，总假定m是正整数。
定义1设f(x) = a n x n+ +a1x+a0是整系数多项式，称f(x) ≡ 0 (mod m) (1) 是关于未知数x的模m的同余方程，简称为模m的同余方程。
若a n≡/0 (mod m)，则称为n次同余方程。
定义2设x0是整数，当x = x0时式(1)成立，则称x0是同余方程(1)的解。
凡对于模m同余的解，被视为同一个解。
同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。
由定义2，同余方程(1)的解数不超过m。
定理1下面的结论成立：(ⅰ) 设b(x)是整系数多项式，则同余方程(1)与f(x) +b(x) ≡b(x) (mod m)等价；(ⅱ) 设b是整数，(b, m) = 1，则同余方程(1)与bf(x) ≡ 0 (mod m)等价；(ⅲ) 设m是素数，f(x) = g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x) ≡ 0 (mod m) 或h(x) ≡ 0 (mod m)107108 的解。
证明 留做习题。
下面，我们来研究一次同余方程的解。
定理2 设a ，b 是整数，a ≡/0 (mod m )。
则同余方程ax ≡ b (mod m ) (2)有解的充要条件是(a , m )∣b 。
若有解，则恰有d = (a , m )个解。
证明 显然，同余方程(2)等价于不定方程ax + my = b ， (3)因此，第一个结论可由第四章第一节定理1得出。
若同余方程(2)有解x 0，则存在y 0，使得x 0与y 0是方程(3)的解，此时，方程(3)的全部解是⎪⎪⎩⎪⎪⎨⎧-=+=t m a a y y t m a m x x ),(),(00，t ∈Z 。
(4) 由式(4)所确定的x 都满足方程(2)。
记d = (a , m )，以及t = dq + r ，q ∈Z ，r = 0, 1, 2, , d - 1，则x = x 0 + qm +r dm x r d m +≡0(mod m )，0 ≤ r ≤ d - 1。
容易验证，当r = 0, 1, 2, , d - 1时，相应的解 dm d x d m x d m x x )1(20000-+++，，，， 对于模m 是两两不同余的，所以同余方程(2)恰有d 个解。
证毕。
在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。
例1 设(a , m ) = 1，又设存在整数y ，使得a ∣b + ym ，则x ≡aym b +(mod m ) 是方程(2)的解。
解 直接验算，有ax ≡ b + ym ≡ b (mod m )。
109注：例1说明，求方程(2)的解可以转化为求方程my ≡ -b (mod a ) (5)的解，这有两个便利之处：第一，将一个对于大模m 的同余方程转化为一个对于小模a 的同余方程，因此有可能通过对模a 的完全剩余系进行逐个验证，以求出方程(5)和(2)的解；第二，设m ≡ r (mod a )，r < a ，则又可继续转化成一个对于更小的模r 的同余方程。
例2 解同余方程325x ≡ 20 (mod 161) (6)解 同余方程(6)即是3x ≡ 20 (mod 161)。
解同余方程161y ≡ -20 (mod 3)，2y ≡ 1 (mod 3)，得到y ≡ 2 (mod 3)，因此方程(6)的解是x ≡3161220⋅+= 114 (mod 161)。
例3 设a > 0，且(a , m ) = 1，a 1是m 对模a 的最小非负剩余，则同余方程a 1x ≡ -b ][am (mod m ) (7) 等价于同余方程(2)。
解 设x 是(2)的解，则由m =][am a + a 1得到 ][][])[(1am b a m ax x a m a m x a -≡-≡-=(mod m )， 即x 是同余方程(7)的解。
但是由假设条件可知同余方程(2)与(7)都有且只有一个解。
所以这两个同余方程等价。
注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。
例4 解同余方程6x ≡ 7 (mod 23)。
解 由例3，依次得到6x ≡ 7 (mod 23) ⇔ 5x ≡ -7⋅3 ≡ 2 (mod 23)⇔ 3x ≡ -2⋅4 ≡ -8 (mod 23)110⇔ 2x ≡ -8(-7) ≡ 10 (mod 23)⇔ x ≡ 5 (mod 23)。
例5 设(a , m ) = 1，并且有整数δ > 0使得a δ ≡ 1 (mod m )，则同余方程(2)的解是x ≡ ba δ - 1 (mod m )。
解 直接验证即可。
注：由例5及Euler 定理可知，若(a , m ) = 1，则x ≡ ba ϕ(m ) - 1 (mod m )总是同余方程(2)的解。
例6 解同余方程81x 3 + 24x 2 + 5x + 23 ≡ 0 (mod 7)。
解 原同余方程即是-3x 3 + 3x 2 - 2x + 2 ≡ 0 (mod 7)。
用x = 0，±1，±2，±3逐个代入验证，得到它的解是x 1 ≡ 1，x 2 ≡ 2，x 3 ≡ -2 (mod 7)。
注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。
例7 解同余方程组⎩⎨⎧≡-≡+)7(mod 232)7(mod 153y x y x 。
(8) 解 将(8)的前一式乘以2后一式乘以3再相减得到19y ≡ -4 (mod 7)，5y ≡ -4 (mod 7)，y ≡ 2 (mod 7)。
再代入(8)的前一式得到3x + 10 ≡ 1 (mod 7)，x ≡ 4 (mod 7)。
即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7)。
例8 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组⎩⎨⎧≡≡)(mod )(mod 2211m a x m a x (9)111 有解的充要条件是a 1 ≡ a 2 (mod (m 1, m 2))。
(10)若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则x 1 ≡ x 2 (mod [m 1, m 2])。
(11)解 必要性是显然的。
下面证明充分性。
若式(10)成立，由定理2，同余方程m 2y ≡ a 1 - a 2 (mod m 1)有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则x 0 ≡ a 2 (mod m 2)并且x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，因此x 0是同余方程组的解。
若x 1与x 2都是方程组(9)的解，则x 1 ≡ x 2 (mod m 1)，x 1 ≡ x 2 (mod m 2)，由同余的基本性质，得到式(11)。
习 题 一1. 证明定理1。
2. 解同余方程：(ⅰ) 31x ≡ 5 (mod 17)；(ⅱ) 3215x ≡ 160 (mod 235)。
3. 解同余方程组：⎩⎨⎧≡-≡+)47(mod 10)47(mod 3853y x y x 。
4. 设p 是素数，0 < a < p ，证明：!)1()2)(1()1(1a a p p pb x a +-⋅⋅⋅---≡-(mod p )。
是同余方程ax ≡ b (mod p )的解。
5. 证明：同余方程a 1x 1 + a 2x 2 + + a n x n ≡ b (mod m )有解的充要112 条件是(a 1, a 2, , a n , m ) = d ∣b 。
若有解，则恰有d ⋅m n -1个解，mod m 。
6. 解同余方程：2x + 7y ≡ 5 (mod 12)。
第二节 孙子定理本节要讨论同余方程组⎪⎪⎩⎪⎪⎨⎧≡≡≡)(mod )(mod )(mod 2211k k m a x m a x m a x 。
(1) 在第一节的例题中，我们已讨论了k = 2的情形。
下面考察一般情形。
定理1(孙子定理) 设m 1, m 2, , m k 是正整数，(m i , m j ) = 1，1 ≤ i , j ≤ k ，i ≠ j 。
(2)记m = m 1m 2 m k ，M i =im m ，1 ≤ i ≤ k ， 则存在整数M i '（1 ≤ i ≤ k ），使得M i M i ' ≡ 1 (mod m i )， (3)M i M i ' ≡ 0 (mod m i )，1 ≤ j ≤ k ，i ≠ j ， (4)并且i ki i i M M a x '≡∑=10(mod m ) (5)是同余方程组(1)对模m 的唯一解，即若有x 使方程组(1)成立，则x ≡ x 0 (mod m )。
(6)证明 由式(2)，有(M i , m i ) = 1，因此利用辗转相除法可以求出M i '与y i ，使得M i M i ' + y i m i = 1，113 即M i '满足式(3)和式(4)。
由式(3)与式(4)，对于1 ≤ i ≤ k ，有x 0 ≡ a i M i M i ' ≡ a i (mod m i )，1 ≤ i ≤ k 。
若x 也使式(1)成立，则x ≡ x 0 (mod m i )，1 ≤ i ≤ k ，因此x ≡ x 0 (mod [m 1, m 2, , m k ])。
但是，由式(2)可知[m 1, m 2, , m k ] = m ，这就证明了式(6)。
证毕。
定理2 在定理1的条件下，若式(1)中的a 1, a 2, , a k 分别通过模m 1, m 2, , m k 的完全剩余系，则式(5)中的x 0通过模m 1m 2 m k 的完全剩余系。
证明 这是第二章第二节习题6的特例。
证毕。
定理3 同余方程组(1)有解的充要条件是a i ≡ a j (mod (m i , m j ))，1 ≤ i , j ≤ n 。
(7)证明 必要性是显然的。
下面证明充分性。
当n = 2时，由第一节例8可知充分性成立。
假设充分性当n = k 时成立。
假设式(7)当n = k + 1时成立。
我们来考虑同余方程组x ≡ a i (mod m i )，1 ≤ i ≤ k + 1。
