离散数学高等里离散数学-课件-CHAPT16.ppt

离散数学 第四篇 代数结构 第十六章 整 数 §16.1 整除性 整除的概念 定义16.1.1：设a, b∈Z，若?c∈Z，使得a=cb，则称b是a的约数或因数，a是b的倍数，并称b整除a，或者a被b整除，记为b|a。 若对任意的c∈Z，a=cb均不成立，则记为b卜a. 定义16.1.2：设b|a但b≠±a, ±1，则称b为a的真约数。 定义16.1.3：设d | a，d | b，则称d为a和b的公因数，记为d = (a, b)。 例如：3 = (6, 9)，4 = (8, 12)，2 = (8, 12)。 整除的基本定理 定理16.1.1：设a, b∈Z，b≠0，则存在着唯一的q, r∈Z，使得a=qb + r，0≤r＜|b|。 整除的基本定理 定理16.1.1：设a, b∈Z，b≠0，则存在着唯一的q, r∈Z，使得a=qb + r，0≤r＜|b|。 整除的性质Ⅰ 设a,b,c∈Z，于是 ⑴±1 | a， ⑵a | 0， ⑶a | a。(特别0|0) ⑷若a|b，b|c，则a|c。 ⑸若a | b，b | a，则 a = ±b。 整除的性质Ⅱ 设a,b,c∈Z，于是 ⑴若a|b，则ac|bc。 ⑵若a|b，则a|bc ⑶若a | b，a | c，则对?p，q∈Z，有a | pb±qc。 ⑷若a | bi， bi，ei∈Z，则a |∑eibi，1≤i≤n。 ⑸若在一个等式中，除某项外，其余各项都是a的倍数，则此项也是a的倍数。 ⑹ 设a = qb + c，于是a，b的公因数就是b，c的公因数，反之亦然。 整除的性质Ⅱ的证明 ⑶若a | b，a | c，则对?p，q∈Z， 有a | pb±qc。 证明：因为a | b，a | c，故?d,e∈Z，使b=da，c=ea，从而，pb±qc=(pd±qe)a。但pd±qe是整数，故a | pb±qc。 ⑷若a | bi， bi，ei∈Z，则a |∑eibi，1≤i≤n。 证明：由 ⑵若a|b，则a|bc和⑶知本式成立。 整除的性质Ⅱ的证明 ⑸若在一个等式中，除某项外，其余各项都是a的倍数，则此项也是a的倍数。即，若 m n ∑bi= ∑cj , bi ,cj∈Z,i=1,…,m , j=1,…,n （*） i=1 j=1 且a|b1,…,a|bi-1,…,a|bi+1,…,a|bm, a|cj, j=1,…,n.则有a|bi 1≤i≤m 证明：由（*）知bi=∑cj-∑bk， j=1,…,n，k =1,…,m,k≠i.由假设及 ⑷知a|∑cj,a|∑bk 再由⑶知a|∑cj-∑bk，即a|bi 整除的性质Ⅱ的证明 ⑹设a = qb + c，于是a，b的公因数就是b，c的公因数，反之亦然。 证明：设d是a,b的公因数，即d|a，d|b，于是?f,g∈Z，使得a=fd，b=gd，由 a = qb + c得fd=qgd+c，再由⑸知d|c，于是d也是b,c的公因数。 反之，设e是b,c的公因数，同理可得e|a，故e也是a,b的公因数。 最大公因数 一个记号：{(a, b)}表示a, b的所有公因数的集合。 定义16.1.4：设d=(a, b)。若对?e=(a, b)，都有e|d，称d为a, b的最大公因数。记为d=gcd(a, b)。 显然,若b|a，则b=gcd(b,a)，若a|b，则a=gcd(a,b)。 由定义及性质1之⑸知，若两个整数的最大公因数存在，则除符号外是唯一的。 定理16.1.2：对任意的a, b∈Z，a≠0或b≠0，有d∈Z，使d = gcd(a, b)。 本定理的证明中所提供的求最大公因数的方法，称为辗转相除法。 定理16.1.2的证明 证明: (gcd(a,b)的存在性)设a卜b且b卜a，由于a|0，故a≠0,b≠0,作下列各式： 定理16.1.2的证明 整数与其最大公因子的关系 定理16.1.3: 设d=gcd(a,b)，则存在s, t∈Z,使得 d = sa + tb。 证明：(1)若a | b，则d = a，于是d = 1·a + 0·b。 (2)若b | a，则类似与(1)有：d= 0·a + 1·b。 (3)若a卜b且b卜a，则由定理16.1.2证明过程，有 a q1 1 b b q2 1 r1 rk–2 qk 1 rk–1 b 1 0 r1 r1 1 0 r2 rk–1 1