同余与同余方程

1、第2章 同余与同余方程在整除的基础上,我们进一步研究同余理论.德国大数学家高斯发明了同余式语言.这使得我们差不多能像处理等式一样来处理整除关系.在本章中,我们将给出同余的基本性质,描述如何进行同余式的算术运算,还将研究含未知数的同余方程,例如线性同余方程.引出线性同余方程的一个例子是这样的一个问题,求使得7x被11除所得余数为3的所有整数x.我们还将研究线性同余方程组,它们来源于古代中国难题:求一个数,它被3,5,7处所得余数分别为2,3,2.我们将学习如何运用著名的中国剩余定理来解像上一难题那样的线性同余方程组.2.1 同余的概念及其基本性质一、同余的概念 本章所介绍的同余这一特殊语言在数论

2、中极为有用,它是由历史上最著名的数学家之一高斯于19世纪初提出的. 同余的语言使得人们能用类似处理等式的方式来处理整除关系.在引入同余之前,人们研究整除关系所用的记号笨拙而且难用.而引入方便的记号对加速数论的发展起了帮助作用.定义1 给定正整数m,称为模,设a, b是整数(1) 如果 ,则称a和b对模m同余,简称同余,记为;(2) 如果 ,则称a和b对模m不同余,记为.例1 下列数中哪些对模7同余: 421, 46, 11, 6, 32, 3解:由,得. 我们有时需要将同余式转换为等式.下面的定理能帮助我们做到这一点.定理1 .证明:若,则,这说明存在整数q, 使得qm=a-b,即.反过来,若

3、存在整数q, 使得,则qm=a-b.于是,. 小结: 二、同余的性质定理2 设m是正整数,模m的同余满足下面的性质:(i) 自反性.若a是整数,则;(ii) 对称性.若a,b是整数,且则;(iii) 传递性.若a,b,c是整数,且,则.所以同余是整数间的一种等价关系. 由定义1知定理2是显然的.定理3 若, 则(i)（可加性）;(ii)（可乘性）.定理3很容易证明,另外利用归纳法不难把定理3推广到n个同余式的情形,且易推出下述结论.推论 设 ,k是整数,n是正整数,则(i) ;(ii) .定理4 设是两个整系数多项式,且满足 那么若,则 定理4由定理3及其推论即可推出.当定理4中条件:同次幂系

4、数关于模m同余时,就称多项式f(x)和g(x)对于模m同余,记为定理5 设,k是正整数,则.定理6设,d是正整数,且,则.定理7若,且设,则,特别地,当时,有.证明:因为,所以有,即,由,得.又因为,故,所以. 这一性质说明:在模m不变的情况下,同余式两边不能随便约去相同的因数,如,但.定理8 若,则. 定理8显然可以推广到任意k个同余式的情形.例2 求的个位数.解:由,得.三、整除性检验利用同余可以导出整数的一些整除特征.设N为正整数,则N可表示为,其中 被2的幂整除的检验:; 被5的幂整除的检验:; 被3,9整除的检验:; 被11整除的检验:; 被7,11,13整除的检验:.四、 弃九验算

5、法在公元9世纪,有个印度数学家名叫花拉子米,写有一本花拉子米算术,他们在计算时通常是在一个铺有沙子的土版上进行,由于害怕以前的计算结果丢失而经常检验加法运算是否正确,他们的检验方式就是采用弃九验算法.实际上,弃九验算法就是利用同余来验算正整数进行算术四则运算的计算结果.下面以乘法为例. 设a,b都是正整数,且ab=p, 不妨记则,所以 当上述同余式不成立时,求得的乘积p就是错误的结果.在实际计算时,还可以利用同余式进行简化. 例5 验算下列算式是否正确 . 解:因为 , , ,而,所以上述算式不正确. 注意:弃九验算法只能知道原题一定是错的或有可能正确,但不能保证一定正确. 例如:检验算式 时,等式两边除以9的余数都是0,但是显然算式是错误的.但是,反过来,如果一个算式一定正确,那么它的等式两端一定满足弃九验算法的规律.这个思想往往可以帮助我们解决一些较复杂的数字谜问题. 另外,可以类似地用此法来检验加法、减法、乘方等算式的计算结果.习题2.11.计算m取何值时，下列各式成立:2.计算m取何值时，下列两式同时成立:一般