同余与同余方程

同余与同余方程 第2章 同余与同余方程 在整除的基础上,我们进一步探讨同余理论.德国大数学家高斯独创了同余式语言.这使得我们差不多能像处理等式一样来处理整除关系.在本章中,我们将给出同余的基本性质,描述如何进行同余式的算术运算,还将探讨含未知数的同余方程,例如线性同余方程.引出线性同余方程的一个例子是这样的一个问题,求使得7x被11除所得余数为3的全部整数x.我们还将探讨线性同余方程组,它们来源于古代中国难题求一个数,它被3,5,7处所得余数分别为2,3,2.我们将学习如何运用闻名的中国剩余定理来解像上一难题那样的线性同余方程组. 2.1 同余的概念及其基本性质 一、同余的概念 本章所介绍的同余这一特殊语言在数论中极为有用,它是由历史上最闻名的数学家之一高斯于19世纪初提出的. 同余的语言使得人们能用类似处理等式的方式来处理整除关系.在引入同余之前,人们探讨整除关系所用的记号笨拙而且难用.而引入便利的记号对加速数论的发展起了帮助作用. 定义1 给定正整数m,称为模,设a, b是整数 1 假如 ,则称a和b对模m同余,简称同余,记为; 2 假如 ,则称a和b对模m不同余,记为. 例1 下列数中哪些对模7同余 421, 46, 11, 6, 32, 3 解由,得 . 我们有时须要将同余式转换为等式.下面的定理能帮助我们做到这一点. 定理1 . 证明若,则,这说明存在整数q, 使得qma-b,即.反过来,若存在整数q, 使得,则qma-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中条件同次幂系数关于模m同余时,就称多项式fx和gx对于模m同余,记为 定理5 设,k是正整数,则. 定理6设,d是正整数,且,则. 定理7若,且设,则,特殊地,当时,有. 证明因为,所以有,即,由,得.又因为,故,所以. ■ 这一性质说明在模m不变的状况下,同余式两边不能随意约去相同的因数,如,但. 定理8 若,则. 定理8明显可以推广到随意k个同余式的情形. 例2 求的个位数. 解由,得. 三、整除性检验 利用同余可以导出整数的一些整除特征.设N为正整数,则N可表示为 ,其中 ① 被2的幂整除的检验; ② 被5的幂整除的检验; ③ 被3,9整除的检验; ④ 被11整除的检验; ⑤ 被7,11,13整除的检验. 四、 弃九验算法 在公元9世纪,有个印度数学家名叫花拉子米,写有一本花拉子米算术,他们在计算时通常是在一个铺有沙子的土版上进行,由于胆怯以前的计算结果丢失而常常检验加法运算是否正确,他们的检验方式就是采纳弃九验算法.事实上,弃九验算法就是利用同余来验算正整数进行算术四则运算的计算结果.下面以乘法为例. 设a,b都是正整数,且abp, 不妨记 则 , , , 所以 当上述同余式不成立时,求得的乘积p就是错误的结果.在实际计算时,还可以利用同余式进行简化. 例5 验算下列算式是否正确 . 解因为 , , , 而,所以上述算式不正确. 留意弃九验算法只能知道原题肯定是错的或有可能正确,但不能保证肯定正确. 例如检验算式 时,等式两边除以9的余数都是0,但是明显算式是错误的.但是,反过来,假如一个算式肯定正确,那么它的等式两端肯定满意弃九验算法的规律.这个思想往往可以帮助我们解决一些较困难的数字谜问题. 另外,可以类似地用此法来检验加法、减法、乘方等算式的计算结果. 习题2.1 1.计算m取何值时，下列各式成立 2.计算m取何值时，下列两式同时成立 一般地，若同时成立，则m要满意什么条件 3.证明对一切整数x都有 4.证明. 7.用弃九法验算下列算式是否有错 8.在算式中中遗漏了一个数字，假如其他数字都是正确的，求遗漏的数字。 5 / 5