一次同余式组解法
摘 要:同余式定义 同余式组有解条件 同余式组解法
关键词:同余式;孙子定理;同余式组有解条件;同余式组解法
引言
在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数.例如问我们现在几点钟，就是用24去除某一个总的时数所得的余数.又如问现在是星期几,就是问用问7去除某一个总的天数所得的余数,同是几点钟或同为星期几,常常生活中有所同样的意义.这样,就在数学中产生了同余的概念.
1预备知识
定义 1 若用f(x)表示多项式011a x a x a n n n n +++-- ,其中i a 是整数;又设m 是一个正整数, 则 f(x)≡0(mod m) (1) 叫做模m 的同余式.若0(mod m),则n 叫做(1)的次数.
2 若a 是使f(a) ≡0(mod m)成立的一个整数,则 x ≡a (mod m) 叫做(1)的一解.
定理 1 一次同余式 ax ≡b(mod m)，a 不同余零模m (2)
有解的充分与必要条件是 (a ,m)|b. 且若(2)有解，则(2)的解数（对模m 来说）为 d=(a ,m).
证明 易知(2)有解的充分与必要条件是 ax-my=b 有解.从而由第二章第一节定理2即知(2)有解的充分与必要条件是(a ,m)|b.
设d=(a ,m).若(2)有解,则由第二章第一节定理1知适合（2）式的
一切整数可以表成 x=1m t+0x ,1m =d
m ,t=0,1,-1,2，-2,… 此式对模m 来说,可以写成 x ≡0x +k 1m (mod m),k=0,1, …,d-1.(3) 但0x +k 1m ,k=0,1, …,d-1 是对模m 两两不同余的,故（2）有d 个解,即(3). 证完 定理2(孙子定理) 设1m ,2m ,…,k m 是k 个两两互质的正整数,m=1m 2m …k m ,m=i M i m ,i=1,2,…,k,则同余式组(1)的解是
X ≡
()m b M M b M M b M M k k k mod '22'211'1+++ , 其中i i M M '≡1(mod i m ) i=1,2,…,k.
证明 由(i m ,j m )=1,i ≠j 即得(i M ,i m )=1,故有第一节定理即知对每一i M ,
有一'i M 存在,使得 i i M M '≡1(mod i m ).另一方面m=i M i m ,因此j m |i M ,i ≠j,故 ()i i i i j j k i j j m b M M b M M mod ''≡∑= 即为(1)的解. 若21,x x 是适合(1)式的任意两个整数，则 (),,,2,1,mod 21k i m x x i =≡
因(i m ,j m )=1,于是),(mod 21m x x ≡故(1)式的解只有(2).
证完 一次同余式组解法 1 孙子定理
2 算术解法
例题 1有三位数的奇妙数字.加上1后可被2整除,加上2后可被3整除,加上3后可被4整除,加上4后可被5整除,加上5后可被6整除,加上6后可被7整除.试问该数是多少?
解 解法1(孙子定理) 设该数为x,则由题意有一次同余组 )7(mod 06),6(mod 05),
5(mod 04),4(mod 03),3(mod 02),2(mod 01≡+≡+≡+≡+≡+≡+x x x x x x
又因).6(mod 1),4(mod 1),2(mod 1≡≡≡x x x
而[],126,4,2=故有).12(mod 1≡x
则有,1+105t=12s+1,有12s-105t=0.
解4s-35t=0,有s=35a,t=4b,则x 可表示为x=420a+1.
又所求数为三位数,则x=421或x=841.
解法 2 （算术解法）能被由2到7为止的任何数均可整除的数为 2*3*4*5*6*7=5040 .但是,其中4可能被2整除,6可被2和3整除,故 3*4*5*7=420 也具有相同的性质.
我们再来看1,它加上1的数可被2整除,加上2的数可被3整除,加上3的数可被4整除,加上4的数可被5整除,加上5的数可被6整除,加上6的数可被7
整除.
于是,1加上420的若干倍的数也具有相同的性质, 故在3位数中有
1+420=421
1+420*2=841
这两个数,就是所求的数. 此外,末尾的数字为1可由
x+1=偶数
x+4=5的倍数导出.
结论
一次同余式组解法可由多种方法解得,孙子定理可以求解但较为繁琐其过程有时还需利用二元一次不定方程求解.而利用算术求解则较为简单.故在求解时应首先观察一次同余式组特征性质以便选取简单方法求解.
参考文献：
(1)(闵嗣鹤,严士键).初等数论.高等教育出版社,2003
(2)[]日中村义作著.鲍重光译.数学谜题的20种解法.北京理工大学出版社,2007。