《《离散数学》课件：5-1-整除性辗转相除》由会员分享，可在线阅读，更多相关《《离散数学》课件：5-1-整除性辗转相除（33页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 数论基础数论基础 1 1第五章第五章 数论基础数论基础 5.1 整除性整除性 辗转相除辗转相除 5.2 互质互质 质因数分解质因数分解 5.3 合同合同 一次同余式一次同余式 5.4 秦九韶定理秦九韶定理 Euler函数函数 5.5 一元高次同余式一元高次同余式 二次剩余二次剩余 2 25.1.1 整除及其性质整除及其性质 定义定义5.1.1 设设a和和b是任意整数，若存在是任意整数，若存在整数整数c，使得使得a=bc，则说则说a是是b的倍数，的倍数，b是是a的因数。或者说的因数。或者说a被被b整除，而整除，而b整除整除a。记为记为b|a。显然，任意数整除显然，任意数整除0，特别
2、，特别0|0；1（-1）整除任意整数。整除任意整数。 0不整除任意非零整数不整除任意非零整数.3 3定理定理5.1.1 对任意整数对任意整数a和和b，b 0，唯一存在一对整数唯一存在一对整数q和和r，使得使得0r|b|，a=qb+r。q称为称为( (不完不完全全) )商数，商数，r称为称为a被被b除的余数。除的余数。证明证明：(1)当当b0时，存在性成立。时，存在性成立。看看函函数数 y=bx, x Z。因因为为b0，所所以以y是是x的的单单调调递递增增函函数数，且且当当x+时时，y+；当当x-时时，y-，从从而而存存在在q，使使得得x=q时时，ya；x=q+1时时y a。即即 bqa，b(q
3、+1) a。令令r=a-bq，则则r0且且r b。于于是是 a=qb+r, 0rb。 4 4定理定理5.1.1 (2)当当b=-b 0时，存在性成立。时，存在性成立。由由( (1) )知，存在知，存在q，r，使得使得a=qb+r，0r b。取取q=-q，r=r，则得则得a=-qb+r =qb+r，0r -b。 综合综合( (1) )，( (2) )对任意对任意b (b 0)，都有都有q，r，使得使得a=qb+r 0r |b| ( )5 5定理定理5.1.1 (3)q和和r的唯一性。的唯一性。设另有一对设另有一对q和和r满足满足 a=qb+r 0 r |b| ()则则() - ( )得得 r-r
4、=(q-q)b，从而有从而有 |r-r|=|q-q|b|。注意到注意到 |r-r| |b| ，而而|q-q| 0为整数，所以必有为整数，所以必有|q-q|=0，从从而而 |r-r|=0。即即 q=q，r=r。所以，唯一性成立。所以，唯一性成立。 6 6由整除的定义，易得如下由整除的定义，易得如下推论推论：b|a，(b 0)当且仅当当且仅当a被被b除的余数为除的余数为0。整除的定义：整除的定义：a=bc定理定理5.1.1：a=qb+r 推论推论 7 7整除的基本性质整除的基本性质 性质性质1 若若a|b，b|c，则则a|c证明：证明：因为因为a|b，b|c，故有整数故有整数d，e使使b=ad，c
5、=be，因之，因之，c=a(de)。而而de是是整数，所以整数，所以a|c。性质性质2 若若a|b，则则a|bc证明：证明：由定义知，由定义知，b|bc。今今a|b，故由故由性质性质1，a|bc 8 8整除的基本性质整除的基本性质 性质性质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 若若a整除整除b1,bn, 则则a|1b1+nbn，其中其中i为任意整数。为任意整数。证明：证明：因为因为a|bi，故由性质故由性质2，a| ib
6、i。因为因为a| 1b1，a| 2b2，故由性质故由性质3，a| 1b1+ 2b2。由此及由此及a| 3b3，又有又有a| 1b1+ 2b2+ 3b3。如此如此类推归纳证明了类推归纳证明了a| 1b1+ nbn。 9 9整除的基本性质整除的基本性质 性质性质5 若在一等式中，除某项外，其余若在一等式中，除某项外，其余各项都是各项都是a的倍数，则此项也是的倍数，则此项也是a的倍数的倍数。证明：证明：这是性质这是性质4的直接推论。的直接推论。例如，在等式例如，在等式b-c=-d+e+f中，设中，设b，c，d，f都是都是a的倍数，求证的倍数，求证e也是也是a的倍数。的倍数。解出解出e得得e=b-c+
7、d-f。由性质由性质4，此式右，此式右边是边是a的倍数，故的倍数，故e是是a的倍数。的倍数。 1010整除的基本性质整除的基本性质 性质性质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，故此二数必然都是，故此二数必然都是 1，因而因而b= a。 1111整除的基本性质整除的基本性质 定义
8、定义5.1.2 若若d是是a的因数也是的因数也是b的因数，的因数，则称则称d为为a，b的的公因数公因数。若。若d是是a，b的的公因数，而公因数，而a，b的任意公因数整除的任意公因数整除d，则称则称d为为a，b的的最高公因数最高公因数。a，b的最的最高公因数通常记为高公因数通常记为d=(a,b)。 1212整除的基本性质整除的基本性质 性质性质7 设设a=qb+c，则则a，b的公因数与的公因数与b，c的公因数是完全相同的。的公因数是完全相同的。证明：证明：若若d是是b，c的公因数，则由上式的公因数，则由上式及性质及性质5，d也是也是a的因数，因而是的因数，因而是a,b的的公因数。反之，若公因数。
9、反之，若d是是a，b的公因数，的公因数，则由上式及性质则由上式及性质5，d也是也是c的因数，因的因数，因而是而是b，c的公因数。的公因数。 1313如果如果a，b有最高公因数，则最高公因数有最高公因数，则最高公因数除符号外除符号外唯一确定唯一确定。证明：证明：若若d和和d都是都是a，b的最高公因数，的最高公因数，则则d|d，d|d，因而由性质因而由性质6知，知，d=d。 1414现在我们来看，是否任意现在我们来看，是否任意a，b有最高公有最高公因数？因数？若若b|a，则由定义易见，则由定义易见，b就是就是a，b的最的最高公因数。同样，若高公因数。同样，若a|b，a 就是就是a，b的的最高公因数
10、。最高公因数。5.1.2 辗转相除辗转相除 今设今设a|b，b|a。因为任意数整除因为任意数整除0，所以，所以a 0，b 0。以以b除除a得商得商q1余数余数r1，以以r1 除除b得商得商q2余数余数r2，以以r2除除r1得商得商q3余余数数r3。如此类推有下列各式：如此类推有下列各式：1515a=q1b+r1b=q2r1+r2r1=q3r2+r3 rk-2=qkrk-1+rk rn-2=qnrn-1+rnrn-1=qn+1rn。 5.1.2 辗转相除辗转相除 (1)1616任意二整数任意二整数a，b有最高公因数。有最高公因数。 上面求最高公因数的方法叫做上面求最高公因数的方法叫做辗转相除辗转
11、相除法法。对。对a，b使用辗转相除得到的最后使用辗转相除得到的最后一个非一个非0余项余项(rn)即为即为a，b的最高公因的最高公因数。数。 定理定理5.1.2 1717任意二整数任意二整数a，b的最高公因数的最高公因数d可以表可以表示为示为a，b的倍数和，即表为下面的形式：的倍数和，即表为下面的形式：d=sa+tb 其中其中 s，t都是整数。都是整数。证明：证明：(方法一）方法一）由辗转相除法知由辗转相除法知d=rn。只需证明对每一只需证明对每一个个i(i=1,n)，ri都可以表示成都可以表示成 ri=sa+tb的形式。的形式。 定理定理5.1.3 1818当当i=1时时, r1=a-q1b。
12、当当i=2时时, r2=b-r1q2=b-(a-bq1)q2=-aq2+b+bq1q2 =-q2a+(1+q1q2)b。假设假设 rm-1，rm-2，3 m n，分别有分别有s, t及及s”, t”使得使得rm-2=s”a+t”b，rm-1=sa+tb，下面说明下面说明rm也可以表示成这种形式。也可以表示成这种形式。rm= -rm-1qm+rm-2 =-(sa+tb)qm+s”a+t”b =(s”-sqm)a+(t”-tqm)b 因此对一切因此对一切i (i=1, , n)成立。成立。 定理定理5.1.3 1919证明：证明：(方法二）方法二）若若a，b中有一个整除另一个，不妨假中有一个整除另
13、一个，不妨假设设b|a，则则d=b=0a+1b，得证。得证。 定理定理5.1.3 现设现设a|b，b|a。由辗转相除得由辗转相除得(1)中各中各式。对式。对(1)中各式各补充一个关于除数中各式各补充一个关于除数的恒等式，如第一式补上的恒等式，如第一式补上b=b，并表示并表示成矩阵形式。成矩阵形式。2020定理定理5.1.3 则由则由(1)(1)的第一式知的第一式知 : :由由(1)(1)的第二式知的第二式知 : :2121定理定理5.1.3 依此类推依此类推 : :令令 2222定理定理5.1.3 又又 则则2323定理定理5.1.3 故故又又 2424定理定理5.1.3 故故2525定理定理
14、5.1.3 因此因此所以，我们有所以，我们有2626定理定理5.1.3 取取k=n，则因则因rn即最高公因数即最高公因数d而得而得 即为所求的形式即为所求的形式这表明，任给两个数，我们都可将它这表明，任给两个数，我们都可将它们的最高公因数表示为它们的倍数和们的最高公因数表示为它们的倍数和的形式，这里需求出的形式，这里需求出n，Sn，Tn。 2727定理定理5.1.3 为能简便地计算它们，让我们看下面的为能简便地计算它们，让我们看下面的等式：等式： 比较最左最右两矩阵的第二列知比较最左最右两矩阵的第二列知:Uk=Sk-1，Vk=Tk-1。 因而，因而， Uk-1=Sk-2，Vk-1=Tk-2 (
15、1)2828再比较这两个矩阵的第一列：再比较这两个矩阵的第一列：Sk=qkSk-1+Uk-1 Tk=qkTk-1+Vk-1 (2)由由(1)式式和和(2)式式得：得：Sk=qkSk-1+Sk-2 Tk=qkTk-1+Tk-2 (3)(1)式在式在k2时成立，时成立，(2)式在式在k 2时成立，时成立，所以所以(3)式在式在k2时成立。时成立。 定理定理5.1.3 2929现令现令S0=U1， T0=V1则则(1)式在式在k=2时也成立，即时也成立，即(3)式在式在k=2时也成立。时也成立。定理定理5.1.3 得得S0=U1=0，S1=1，T0= V1 =1，T1=q1 根据这个初值及根据这个初
16、值及(3)式，便可求出任意式，便可求出任意的的Sk，Tk。 由由3030例例5.1.2求求301和和133的最高公因数并表为它们的倍的最高公因数并表为它们的倍数和。数和。解：解：用辗转相除法求最高公因数逐次得商用辗转相除法求最高公因数逐次得商及余数并计算及余数并计算Sk，Tk如下表所示：如下表所示： k01234qk2314rk352870Sk0134Tk12793131例例5.1.2求求301和和133的最高公因数并表为它们的最高公因数并表为它们的倍数和。的倍数和。解：解：因之，最高公因数为因之，最高公因数为7，表为原二，表为原二数的倍数和如下：数的倍数和如下：7=(-1)2 4 301+(-1)3 9 133 =4 301+(-9) 1333232作业作业11P160-23333
