《离散数学》课件：5-1整除性辗转相除

《《离散数学》课件：5-1整除性辗转相除》由会员分享，可在线阅读，更多相关《《离散数学》课件：5-1整除性辗转相除（32页珍藏版）》请在文档大全上搜索。

1、5.1 整除性整除性 辗转相除辗转相除 5.2 互质互质 质因数分解质因数分解 5.3 合同合同 一次同余式一次同余式 5.4 秦九韶定理秦九韶定理 Euler函数函数 5.5 一元高次同余式一元高次同余式 二次剩余二次剩余 定义定义5.1.1 设设a和和b是任意整数，若存在整数是任意整数，若存在整数c，使得使得a=bc，则说则说a是是b的倍数，的倍数，b是是a的因的因数。或者说数。或者说a被被b整除，而整除，而b整除整除a。记为记为b|a。显然，任意数整除显然，任意数整除0，特别，特别0|0；1（-1）整）整除任意整数。除任意整数。 由整除的定义，易得如下推论：由整除的定义，易得如下推论：b

2、|a，(b 0) 当且仅当当且仅当a被被b除的余数为除的余数为0。 性质性质1 若若a|b，b|c，则则a|c证明：因为证明：因为a|b，b|c，故有整数故有整数d，e使使b=ad，c=be，因之，因之，c=a(de)。但但de是整数，所以是整数，所以a|c。性质性质2 若若a|b，则则a|bc证明：由定义知，证明：由定义知，b|bc。今今a|b，故由性质故由性质1，a|bc 性质性质3 若若a|b，a|c，则则a|b c。证明：因为证明：因为a|b，a|c，故有整数故有整数d，e使使b=ad，c=ae。因之，因之，b c=a(d e)。但但d e为整数，所以为整数，所以a|b c。性质性质4

3、 若若a整除整除b1,bn, 则则a|1b1+nbn，其中其中i为任意整数。为任意整数。证明：因为证明：因为a|bi，故由性质故由性质2，a| ibi。因为因为a| 1b1，a| 2b2，故由性质故由性质3，a| 1b1+ 2b2。由此及由此及a| 3b3，又有又有a| 1b1+ 2b2+ 3b3。如此类推归纳证明了如此类推归纳证明了a| 1b1+ nbn。 性质性质5 若在一等式中，除某项外，其余各若在一等式中，除某项外，其余各项都是项都是a的倍数，则此项也是的倍数，则此项也是a的倍数的倍数。证明：这是性质证明：这是性质4的直接推论。的直接推论。例如，在等式例如，在等式b-c=-d+e+f中

4、，设中，设b，c，d，f都是都是a的倍数，求证的倍数，求证e也是也是a的倍数。解出的倍数。解出e得得e=b-c+d-f。由性质由性质4，此式右边是，此式右边是a的倍的倍数，故数，故e是是a的倍数。的倍数。 性质性质6 若若a|b，b|a，则则b= a。证明：由条件知，或者证明：由条件知，或者a=b=0，或者或者a，b都不为都不为0。若。若a=b=0，则则b= a自然是对的。自然是对的。若若a，b都不是都不是0。因为。因为a|b，b|a，故有整数故有整数d，e使使b=ad，a=be，从而从而a=ade。消去消去a得得1=de。今今d，e是整数而相乘得是整数而相乘得1，故此二数，故此二数必然都是必

5、然都是 1，因而，因而b= a。 定义定义5.1.2 若若d是是a的因数也是的因数也是b的因数，则的因数，则称称d为为a，b的公因数。若的公因数。若d是是a，b的公因数，的公因数，而而a，b的任意公因数整除的任意公因数整除d，则称则称d为为a，b的最高公因数。的最高公因数。a，b的最高公因数通常记的最高公因数通常记为为d=(a,b)。 性质性质7 设设a=qb+c，则则a，b的公因数与的公因数与b，c的公因数是完全相同的。的公因数是完全相同的。证明：若证明：若d是是b，c的公因数，则由上式及性的公因数，则由上式及性质质5，d也是也是a的因数，因而是的因数，因而是a,b的公因数。的公因数。反之，

6、若反之，若d是是a，b的公因数，则由上式及性的公因数，则由上式及性质质5，d也是也是c的因数，因而是的因数，因而是b，c的公因数。的公因数。 最高公因数的定义只是说，如果有那样的最高公因数的定义只是说，如果有那样的d，则则d叫做叫做a，b的最高公因数。对于任意的的最高公因数。对于任意的a，b是否有那样的是否有那样的d呢？现在还不知道，等下呢？现在还不知道，等下面再研究。不过，有一点是容易说明的：面再研究。不过，有一点是容易说明的：如果如果a，b有最高公因数，则最高公因数除有最高公因数，则最高公因数除符号外唯一确定。事实上，若符号外唯一确定。事实上，若d和和d都是都是a，b的最高公因数，则的最高