数论ch1-2节.pptVIP

Ch1 整数的唯一分解定理 内容简介 整除, 因数, 倍数 最大公因数和Euclid算法 最小公倍数 素数和合数 整数的唯一分解定理 不定方程 二、最大公因数 定义2.1 设a1, a2, …, an是n个不全为零的整数. 若整数d 是它们之中每一个的因数, 那么d 就叫做a1, a2, …, an的一个公因数. 定义2.2 整数a1, a2, …, an的公因数中最大的一个叫做最大公因数, 记作(a1, a2, …, an). 最大公因数(greatest common divisor) 如果(ai, a j) = 1，1 ? i, j ? k，i ? j，则称a1, a2, ?, ak是两两互素的（或两两互质的）。 若(a1, a2, …, an) ? 1, 称a1, a2, …, an 互素. 显然，a1, a2, ?, ak两两互素可以推出(a1, a2, ?, ak) = 1，反之则不然. 思考：公因子和最大公因子之间的关系. 最大公因数常用推论等式 (ⅰ) (a1, a2, ?, ak) = (|a1|, |a2|, ?, |ak|)； (ⅱ) (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|； (ⅲ) (a, b) = (b, a)； (ⅳ) 若p是素数，a是整数，则(p, a) = 1或p?a； 最大公因数的性质 定理2.1 设a和b都是正整数, 且a b, a ? bq+r, 0 r b 其中q和r都是正整数. 则: ① (a,b) ? (b,r) ; ②若(a,b) ? d, 则 (a/d, b/d) ? 1. 定理2.1的证明: 证 ①因为(a,b)|a, (a,b)|b, 故 (a,b)|(a?bq), 即(a,b)|r, 显然(a,b)|b, 故(a,b)|(b,r) 从而 (a,b) ? (b,r). 同理可证(b,r) ? (a,b). 故有(a,b) ? (b,r). ②假设c ? (a/d,b/d). 显然c ? 1, 下面只要证c ? 1. 因c|(a/d), c|(b/d), 不妨设a/d ? cu, b/d ? cv, 即 (cd)u ? a, (cd)v ? b. 故cd是a和b的公因数, 从而cd ? (a,b), 即cd ? d. 又因为d 0, 故c ? 1, 从而 c ? 1. 定理2.2 若任给整数a ?0, b ?0, 则(a, b)就是(3)中最后一个不等于零的余数, 即 (a, b) ? rn . 证 由定理2.1可得 rn ? (0, rn) ? (rn, rn?1) ? ??? ? (r2, r1) ? (r1, b) ? (a, b). # 定理2.3 任给整数a ?0, b ?0, 存在两个整数m, n,使得 (a, b) ? ma ? nb. 推论 设d 是整数a, b的任一公因数, 则d | (a, b). 证 因为 故必然存在整数 m, n, 使得 (a,?b)???ma???nb. 定理2.1给出了求两个数公因子的一种算法：辗转相除法。 利用最大公因数—绝对最小剩余带余除法 欧几里德算法和扩展的欧几里德算法 辗转相除法(Euclid算法) 设a ? b 0, 由带余除法可以得到下列等式 (3) Euclid算法伪码表示 输入a和b, a,b ? 0; 输出GCD ? gcd(a,b). Eucid(a,b,GCD) IF b ? 0 THEN GCD : ? a /* 设gcd(0,0) ? 0 */ WHILE b 0 /*若 b 0, 继续循环*/ BEGIN q : ? [a/b] /*商*/ r : ? a－qb /*余数*/ GCD : ? b /*暂存*/ a : ? b /*为下次辗转相除准备*/ b : ? r END 解: 因为 288 ? 158 ?1 ? 130 158 ? 130 ? 1 ? 28 130 ? 28 ? 4 ? 18