(完稿)一元一次同余方程的解理论及其应用.doc

内江师范学院本科毕业论文
摘要：首先介绍了一元一次同余方程的定义，分别讨论了系数在各种情形下有解的充分必要条件，并给出了详细的证明．在将多个解的一元一次同余方程转化成唯一解的一元一次同余方程后，具体的给出了求解一元一次同余方程的七种方法，它们是公式法分别观察法、分子分母化解法、辗转模数减小法、转化为不定方程求解法、利用矩阵读解法、均为奇数的系数缩减法等．并结合了一系列较为典型的例题对这些方法的运用进行了深入的分析，比较，综合．从而说明了在解一元一次同余方程时，对于不同的系数选择和运用恰当的方法，可以收到很好的效果．其次给出了解理论的应用，主要是应用在求解非标准型一元一次同余方程组和一次不定方程两个方面，并结合例题进行了详细的阐述．
关键词：一元一次同余方程； 解理论；应用

Abstract: This paper introduced a Yuan congruence equation definition at first, discussed the necessary and sufficient condition for the equation that the coefficient has different form has solution, and has proved detailed After will be equation to transform the a Yuan congruence equation has many solutions into the a Yuan congruence equation has unique solution, gave seven methods solve a Yuan congruence equation detaided, namely the formula law, the method of inspection, the molecular denominator melt law, go through many places the modulus to reduce the law, to transform to the indefinite equation solution law, the solution using the matrix, for the odd number coefficient flop-out method and so on. And unified a series of typical questions to carry on the thorough analysis,comparetion and synthesis to these methods ,. Thus explained when solves a Yuan congruence equation, regarding the different coefficient choice and the utilization appropriate method, may receive the very good effect..Next gives the result theory’s application, mainly is two aspects’ application that is solving a non-standard Yuan congruence system of equations and indefinite equation, and unified the sample question to carry on the detailed elaboration.
Key words: Yuan congruence equation　Cleavage theory　 using

一元一次同余方程的解理论及其应用（定稿）
1 引言
同余方程是初等数论中的一个重要问题.其中的内容包括一元一次同余方程（组）、二次同余方程、高次同余方程等.一元一次同余方程（形如），其解法是初等数论中很基础也是很重要的内容之一.关于它的解理论教材中给出了几种较为传统的方法，如欧拉定理法（也叫公式法）、系数模的缩减法等。初等数论的研究者们也给出了一些解法,如沈洁,刘荣英在[1]中就给出了五种求解一元一次同余方程的方法。唐宗明在[2]中详细的给出了运用矩阵的初等变换解一元一次同余方程（组）.而李秀丽，郭爽在[3]中则给出了一些特殊系数的处理方法. 并讨论了解理论在求解一元一次同余方程组,二元一次不定方程,以及初等数学中的一些题目等.本论文对一元一次同余方程的解理论以及解理论的应用这两个方面详细的进行归纳、总结.
2 预备知识
2.1 一元一次同余方程的慨念
定义2.1　设, 为整数，是一个正整数，把
，　 (1)
叫做一元一次同余方程
定义2.2　若是使成立的一个整数，则叫做(1)的一个解.
2.2　一元一次同余方程有解的充要条件及解原理
　要解形同(1)这个同余方程，首先就要知道在什么样的情况下(1)有解，以及有多少解的问题.
定理2.3 一元一次同余方程(1)有解的充要条件是:
.
证　很容易看出(1)有解的充分必要条件是有解.
若有一整数解,设为,则
，
但整除及,因而整除,故条件的必要性获证
反之若,则.所以存在两个整数满足下列等式
.
令,即得,故有整数解.
设，若(1)有解,可知适合(1)式的一切整数可以表示成
，
此式对于模来说,可以写成

由于是对模两两不同余的,故(1)有个解.
证完.
那么对于一元一次同余方程(1)的所有解有如下定理：
定理2.4 设, 则当 (不整除)时，方程无解；当d=1时，方程
有唯一的解；当>1时且(整除) 时方程有 个解.它们是：

(2)
其中是方程(1)的一个特解.
因此，当一元一次同余方程有解并且不只一个解时，关键就是求出方程(1)的一个特解：
.
因为在时，方程(1)有解，
令 ，则有, , ，
所以 .
(3)
此时(3)有唯一解，把它叫做(1)的一个特解.
3 一元一次同余方程的解理论
现在对于任意给定的方程(1),首先就要判定它有没有解即是否整除；如果整除,就有解；否则无解. 若则方程有唯一的一个解. 若整除且比1要大,那么(1)就有个解.此时由定理2.4只需求出(3)的解,然后代入到(2)中,就可以把(1)的全部解求出来了.因此求解许多解的一元一次同余方程总可以转化成求解一元一次同余方程(3)，下面就系统介绍几种求解一元一次同余方程(3)的方法.
3.1 公式法
定义3.1 欧拉函数是定义在正整数上的函数，它在正整数上的值等于序列 中与互质的数的个数.
利用欧拉函数，方程(3)的唯一解为：

注：这种用公式直接计算得到特解，然后回代到(2)，表面上看很简单，其实只要，中的任何一个数较大时，计算量都很大.必须借助计算机等工具或者利用高级算法才能解决.
3.2 观察检验法
首先判断是否有解,然后把模的完全剩余系逐个代入方程进行检验，从而求出一元一次同余方程的解.
例1 解同余方程
解 方程只有一个解，的完全剩余系是，我们就从中寻找，带入检验符合题目的要求，是它的解.
我们在比较看方程此时就有两个解.
注：这种方法一般应用于当模相对较小的一元一次同余方程，而在系数较大的时候，可以利用同余的性质，将同余方程的系数减小.进而用观察法可快速地得出方程的解.

3.3 分子分母化简法
这种方法都是先把方程(3)写成的形式，然后再通过两种方法共同作用化分为整，解决问题，具体步骤如下：
(1)先把方程(3)写成的形式. (2)然后将分子或分母加上或减去的整数倍；或分子，分母同乘以不为零的整数或约去一个与模互素的数，一直到出现整数为止.

例 2 解方程103x57(mod211)
解 因为（103，211）=1，故方程有唯一解.所以

所以原同余方程的解为.
注：这两种办法可以单独进行，也可以交叉进行.
3.4 辗转模数减小法
假设同余方程（3）的解为，利用余数定理和同余性质，必然存在一个使得，也就是同余方程 的解变成了，而同余方程的模显然比要小，同样经过几次的辗转变换化简后，模数就一直在减小中，直到可以观察得出结果为止，然后把所得的结果逐个替换带入前面一个方程中，最后求出即为我们要的结果.
例3 解方程
解 因为（37，107）=1，则方程有唯一解
由原方程有， 化简可得
， （1）
再由（1）变化得 化简可得
， （2）
再由（2）变化得 化简可得
， （3）
再把递推带入（2）可得
，
所以再带入（1）可得
，
所以最后在带入原方程得
， 所以
.
于是原方程的解为： .
注：辗转模数减小法的好处就是在回代递推的过程中起到了一个检验的作用，如果求出的不是整数的话，就要从头进行检查了.在运用该方法的时候一定要仔细核对,小心代换.

3.5 转化为不定方程求解法
对于一元一次同余方程，其中，由于故存在，使得，即
，
所以 ，
所以原同余方程的解为

这种解法实际是把求解同余方程转化成了求解 中的一个特解.解出就可以直接的得到一元一次同余方程的解.
例 4 解方程
解 因为（26，31）=1 （26，11）=1， 故原方程可以化成求解不定方程，即求解不定方程.
由观察法可知 ，
又由同余的性质可知：，
所以 为原方程的解.
3.6 利用矩阵读解法
一元一次同余方程还可利用高等代数中的矩阵求解，具体的做法是：对同余方程(3)，先写出矩阵，然后对其实施关于该矩阵的初等行变换，当右上角（或右下角）出现时，那么左边对应的数就是(3)的解.
例 5 解方程
解 因为（589，817）=19，并且
589=1931 817=1943 1026=1954，
所以原一元一次同余方程可化为

从而可化为矩阵求解
，
因此 解是
.
于是，由(2)可知原方程的解是

其中
注：矩阵读解法是根据转化不定方程法总结而来，这是因为不定方程同样可以写成一个矩阵的形式来求出它的一组特解.
3.7 均为奇数的系数缩减法
在求解一元一次同余方程时,对于一些特殊的系数,例如 均为奇数,形如的一元一次同余方程，当传统的方法不便求解时,可用一些特殊的方法来求解方程.下面我们具体来看这两种情况.
(1)当，时，因为均为奇数,对于方程，
设 则 或 ,若的奇偶性相反,则就是4的倍数,若的奇偶性相同,则就是4的倍数,那么此时可以把方程变为.然后两边同时除以4,在变形除4以后, 则系数逐渐缩减,重复以上的步骤直到问题变得较容易解为止.
(2)当,时,因为均为奇数,对于方程 ，
设，若的形式相同,即或,此时将方程变为,两边再除以3的倍数；若的形式不同,即或,此时将方程变为,两边同时除以3的倍数，则系数逐渐缩减,重复以上的步骤直到问题变得较容易解为止.
例6 解同余方程 （1）； （2）
解 （1）因为,123,337,均为奇数,所以有

　（2）因为,124,337,均为奇数,所以有

注：这两种关于方程的解法,只适用于这种特殊形式的一元一次同余方程,它的优势在于化解的过程中,模始终都保持不变.
4 一元一次同余方程解理论的应用
一元一次同余方程解理论作为同余方程的基础，主要用于解多元高次同余方程(组)例如解一元一次线形同余方程组等.在解决初等数学的一些问题中也有相关的应用,例如寻求和证明算术中的一些整除规律,用于处理不定方程等.下面就给出解理论的应用.

4.1 在解一元一次同余方程组中的应用
在这里讨论的一元一次同余方程组主要是形如
　 (4)
的同余方程组．在我国古代的《孙子定理》中就已经很好解决了这种形式的问题了,这就是著名的孙子定理．
定理4.1.1 设是个两两互质的正整数,
，则同余式组(4)的解是，其中

方程（4）是定理的标准型，下面主要讨论的是非标准型．
(5)
前者是标准型,可以应用孙子定理直接的求出来，而非标准型（5）则不能直接的用公式求出来，但可以利用解理论转化为标准型，然后再用孙子定理求解．
例7 解方程组

解 由方程组的第一式,第二式,第三式分别可以得到
.
现在我们就可以利用孙子定理直接求解了．因为

所以
再由可以求得
.
故求得原方程组的解为
.
注：当一元一次方程组不是标准形式时，一定要运用一元一次同余方程的解理论把它化成标准的求解形式．

4.2 　求解不定方程
对于一次不定方程的求解已有一套完整的理论来解决，但是一些不定方程的问题，如果把它转化成一元一次同余方程来求解则更为简捷．具体步骤为把不定方程转化成 ，然后解用余方程得到，最后再把它转化成并带入中解出y的值，就得到不定方程的解．
例8 解不定方程 .
解 将原方程化成 ，而此方程等价于
，
利用2.6的矩阵读解法很快就可以求出
，
从而 ， 代入原方程可解得
，
故原方程的解为 ．
注：特别是对于其他较复杂的不定方程时，若用一般方法求解有困难时，用一下同余方程的解理论，往往可以起到很好的效果．

5 结论
通过对一元一次同余方程解理论极其应用的初步研究，基本掌握了形如方程的系统解理论．对于不同的系数关系，要根据实际的情况找出不同的方法求解．在解理论方面归纳了7种方法，首先给出了一元一次同余方程的定义，在此基础上讨论它有解的条件．后面则分别给出了(1)公式法,(2)观察检验法,(3)分子分母化简法，(4)辗转模数减小法，(5)转化为不定方程求解法，(6)利用矩阵读解法，(7)均为奇数的系数缩减法，等各种具体的方法.在每一种方法后面都给了一道详细的例题论证该种方法的应用.
而在解理论的应用部分，我只是从求解一元一次同余方程组和一次不定方程这两个方面进行了较简单的论述.至于解理论能否在高次多元同余方程中以及在初等数学中的应用都没有讨论.

[参考文献]
[1] 沈洁,刘荣英.一元一次同余方程的解法初探[J]．郧阳师范高等专科学校学报，2002， 22(4)：18－19.
[2] 唐宗明.矩阵初等变换在解同余方程中的应用[J].西藏科技, 2002, 9：36－38.
[3] 李秀丽,郭爽.关于一次同余方程解法的探讨[J]．大庆师范学院学报， 2006， 26(2)： 20-21.
[4] 闵嗣鹤,严士健.初等数论[M].北京：高等教育出版社，2003：
[5] 潘承洞,潘承彪.简明数论[M].北京：北京大学出版社，1998：
[6]徐彦明.一次同余方程的求解技巧[J].高等数学研究,2003, 6(2)：29-31.
[7] 彭敦刚,李德水.同余方程[J]．高等函授学报（自然科学版）， 1993，3：24－27.
[8]林晓燕.谈同余理论在初等数学中的几点应用[J]．怀化师专学报，1995，14(1)： 102-104.
[9]陈志云,程敬荣.同余关系在初等数学中的应用[J]．高等函授学报，2001，14(6)： 9-12.

后记：从查阅资料、翻阅书籍、整理资料到写出初稿，再经过反复的修改花了不少时间和精力．在写作初期首先遇到的问题就是从众多的资料中不知道哪些才是我所需要的，写作中又感觉到整篇的谋篇布局、章节的划分、格式的规范都无从着手，再后来的修改、排版、打印也用时不少．尽管花了这么多时间反复修改才做完这篇论文，但我所学到的东西更多.在知识上,我对一元一次同余方程的解理论有了更深入的理解，并在此基础上将该解理论做了简单应用处理．在生活中，我认为做任何事情都应有专心至致、精益求精的态度．特别是对待学习，更应该有精益求精、勤奋塌实的精神．与此同时，对论文格式有了详细的了解，学习了论文的标准格式，论文的标准框架以及论文的写作中常遇见的问题和解决办法，并亲自做了这方面的工作．
我的指导老师龚小兵老师在整个论文写作过程中给我提出了许多宝贵建议，并给我进行了大量细致的指导，在此致以衷心的感谢．还要感谢我的同学蒋良勇给我提供电脑，以及室友张射乾，黄海明的帮助。他们做了大量的工作，特别是后两者细心的帮助和论文初期的讨论批评，给了我很大的帮助。一并致以深深的谢意．
写这篇文章让我体会到了细心对待每个环节是作好一件大事不可缺少的、必备的素质．当然，由于初次写作，水平有限，论文可能还有许多的错误,不当之处还望大家批评指正，以求不断完善．
- 11 -