一次同余式组解法.docVIP

一次同余式组解法 摘 要:同余式定义 同余式组有解条件 同余式组解法 关键词:同余式;孙子定理;同余式组有解条件;同余式组解法 引言 在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数.例如问我们现在几点钟，就是用24去除某一个总的时数所得的余数.又如问现在是星期几,就是问用问7去除某一个总的天数所得的余数,同是几点钟或同为星期几,常常生活中有所同样的意义.这样,就在数学中产生了同余的概念. 1预备知识 定义 1 若用f(x)表示多项式,其中是整数;又设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=t+,=,t=0,1,-1,2，-2,… 此式对模m来说,可以写成 x≡+k (mod m),k=0,1, …,d-1.(3) 但+k,k=0,1, …,d-1 是对模m两两不同余的,故（2）有d个解,即(3). 证完 定理2(孙子定理) 设,,…,是k个两两互质的正整数,m=…,m=,i=1,2,…,k,则同余式组(1)的解是 X≡, 其中≡1(mod) i=1,2,…,k. 证明 由(,)=1,ij即得(,)=1,故有第一节定理即知对每一,有一存在,使得 ≡1(mod).另一方面m=,因此|,ij,故 即为(1)的解. 若是适合(1)式的任意两个整数，则 因(,)=1,于是故(1)式的解只有(2). 证完 一次同余式组解法 1 孙子定理 2 算术解法 例题 1有三位数的奇妙数字.加上1后可被2整除,加上2后可被3整除,加上3后可被4整除,加上4后可被5整除,加上5后可被6整除,加上6后可被7整除.试问该数是多少? 解 解法1(孙子定理) 设该数为x,则由题意有一次同余组 故由孙子定理有 除数 余数 最小公倍数 衍数 乘 率 各总 答数 最小答数 3 1 3*5*7=105 5*7 2 35*2*1 106 1 5 1 7*3 1 21*1*1 7 1 3*5 1 15*1*1 又因 而故有 则有,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