一次同余式与一次同余式组的解的讨论摘 要: 这篇文章先给出有关同余式、同余式的解的概念，并在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)的解。
若12,x x 是适合(2)式的任意两个整数，则12(mod )(1,2,,).i x x m i k ≡=又由于(,)1,i j m m i j =≠，于是12(mod )x x m ≡，故(2)仅有解(3)。
3一次同余式定理3.1 若(),1,|a m d d =>,b 则(mod )ax b m ≡无解。
证明 若有解，即可得()mod .ax b m ≡而|,d a 于是有0(mod ).b d ≡而这与|,d b 相矛盾，所以同余式无解。
定理3.2 设(,)1,0a m m =>，则同余式(mod )ax b m ≡ (4)有唯一解 ()1(m o d ).m x b am ϕ-≡ 证明 由于1,2,,m 组成一组模数m 的完全剩余系，(,)1a m =，故,2,,a a m a 也组成模数m 的一组完全剩余系，故其中恰有一个数设为aj ，适合(mod ),(mod )aj b m x j m ≡≡就是(4)的唯一解。
方法一 由定理2.1知 ()()()1mod .m m a x ba m ϕϕ-≡。
从而()()1mod m x ba m ϕ-≡为所求的解。
即原命题成立。
方法二因为(),1a m =.由定理(若(),a b d=由最大公因数性质可知必有二数,s t 使 1.as bt+=)知必有二数s t ，使1as mt +=，即()1mod .as m ≡ 故由()mod asx bs m ≡知同余式(4)的解为 ()mod .x bs m ≡定理3.3 设(,),0a m d m =>，同余式(4)有解的充分必要条件是|d b ，且恰有d 个解。
证明 若(4)有解，则由|,|d a d m 推出|d b 。
如果|d b ，则,1a m d d ⎛⎫= ⎪⎝⎭，故同余式mod a b m x d d d ⎛⎫≡ ⎪⎝⎭①有一组解，即同余式(4)有一组解。
若整数c 适合(4)，c 也适合同余式①；反之，若c 适合同余式①，c 也适合同余式(4)。
设t 适合①，则①有唯一解 (m o d )mx t d≡，即全体整数,0,1,2,,mt k k d+⋅=±±对模数m 来说，恰可选出d 个互不同余的整数,,2,,(1).m m mt t t t d d d d ++⋅+- ②这是因为对于mt k d +，设,0k qd r r d =+≤<代入得()(mod ).m m m mt k t qd r t r qm t r m d d d d+⋅=++=++≡+又若 ()0,0,mod m me df d t e t f m d d≤<≤<+≡+，则推出f e =.这就证明了(4)的任一解恰与②中的某一数模数m 同余，而②中的d 个数，又模数m 两两互不同余，即知(4)恰有d 个解。
一般地，我们有定理3.4 设1k ≥，同余式110(mod )k k a x a x b m +++≡ (5)有解的充分必要条件是 ()1,,,|.k a a m b (6) 若条件(6)满足，则(5)的解数为()11,,,k k m a a m - 。
证明 现用归纳法来证明。
由定理3.2知当1k =时结论显然成立。
设()()1111,,,,,,,k k a a m d a a m d -== ，则()11,d a d =。
由定理 3.3知 ()10m o k k a x b d +≡ （ⅰ） 有d 个解()()()()11111mod mod mod 1mod k k k d dx t d x t d x t d d d d≡≡+≡+- ，，,， 从而对模数m 来说有1md d ⋅个解：1111111(mod ),(mod ),,(1)(mod ),(1)(mod ),,(1)(1)(mod )k k k k k x t m x t d m mx t d m d d x t d m d d mx t d d m d d ≡≡+≡+-≡+-≡+-+-对（ⅰ）的一个解k x ，设11n k a x bb d +=， 由归纳法假定，1111110(mod )k k a x a x b d m --+++≡的解数为 22111(,,,)k k k m a a m m d ---= ， 故(5)的解数为2111k k mm d d m d d --⋅⋅=. 例1解同余式 ()11175mod 321.x ≡解 因为()111,3213,3|75,≡故同余式有解，且化为()3725mod107.x ≡ 故 ()257532899m o d 107.371114x -≡≡≡≡-≡ 于是原同余式有三个解：()99,206,313mod321.x ≡ 例2解同余式()286121mod341.x ≡解 因为()286,34111,11|121,≡故同余式有解，且化为()2611mod31.x ≡故 ()11204m o d 31.265x -≡≡≡- 于是原同余式有三个解：()4,35,66,97,128,159,190,221,252,283,314mod341.x ≡4一次同余式组定理4.1 设12,m m 是两个正整数，同余式组()()1122mod mod x b m x b m ≡⎧⎪⎨≡⎪⎩(7) ① 若()12,|m m 12b b -，则同余式组(7)无解。
② 若()1212,|m m b b -，则同余式组(7)有以[]12,m m 为模的一类剩余解。
证明 ①满足同余式()11mod x b m ≡的数为 1,x b m t t Z ≡+∈ ⑴ 并且满足同余式 ()22mod x b m ≡， 则有 ()1122mod b m t b m +≡即 ()1212m o d m t b b m≡- ⑵ 由于()12,|m m 21b b -,所以同余式()22mod x b m ≡无解，即同余式组无解。
③ 若()1212,|m m b b -，则可设()11222112,,,, 1.m m d m m d b b bd m m ''''==-==由⑵得 ()12mod m t b m ''≡ ⑶因为()()1212m m m m dd ''==，d ，，故()121m m ''=，，所以⑶式有一个解。
设()2m o d t b m '≡ 从而⑵有d 个解()()222,,,1mod t b b m b d m m ''≡++-将2,t b m Z λλ'=+∈代入⑴有 ()1121112.x b m b m b bm m m λλ''=++=++又[]121212,m m m m m m d'== []()1112m o d ,x b b m m m ∴=+ 由于11,b m 是给定的，而且b 是唯一确定的，从而同余式组有唯一的解。