数论ch1-1节.pptVIP

整除的性质（设a, b, c均为整数） 若a|b且b|a, 则a＝±b。 若a|b, 则a|bc。 度量 若a|b, 则|a|≤|b|。 若a|b, 则(b/a)|b。 Ch1 整数的唯一分解定理 内容简介 整除, 因数, 倍数 最大公因数和辗转相除法(Euclid算法) 最小公倍数 素数和整数的唯一分解定理 素数分布和素性判别 不定方程 一 、 整除性 约定：集合Z={....-3,-2,-1,0,1,2,3.....}为整数集. 定义1.1 设 a,b为整数，b≠0. 若有一整数q, 使得 a = bq, 则称 a是b的倍数，b是a的因数 并称b整除a, 记为b|a, 可形式地表示为: b|a:=(?q)(a = bq) 若b不能整除a，记为b?a. 若a=bq,且b既非a又非1, 则称b是a的真因数. 显然每个非零整数a都有约数 ?1，?a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。 被2整除的整数称为偶数，不被2整除的整数称为奇数。 定义1.2 若整数a ? 0，?1，并且只有约数 ?1和 ?a，则称a是素数（或质数）；否则称a为合数。 以后在本课程中若无特别说明，素数总是指正素数。 整除的性质（设a, b, c均为整数） 传递性 若a|b且b|c, 则a|c。 可乘性 若a|b, 则ca|cb; 可约性 若ca|cb, c≠0 则a|b。 可加性 对任意整数k和l, 若a|b且a|c, 则a| kb±lc。 例1.1 证明任何奇数的平方减一恒为8的倍数. 例题 证：(分析) 要证8 | (2n ? 1)2 ? 1, 即 8 | 4n2 ? 4n=4 n(n ? 1), 只需证2 | n(n ? 1). 因为2 | n(n ? 1), 所以8 | 4n(n ? 1) ? (2n ? 1)2 ? 1. 证：因为p|10a?? b, p|10c ? d, 而 ad ? bc = c(10a?b) – a(10c ?d), 故p | ad ? bc. 例1.2 证明若p|10a?b, p|10c?d, 则p|ad?bc. 二、带余除法 定理1.2 设a、b是两个整数, 其中b 0, 则存在唯一确定的两个整数q和r, 使得下式成立 a = bq + r (1) 0 ? r b (2) 证明：存在性, 构造整数序列 唯一性, 反证法 定理1.2证明 存在性 若b?a，a = bq，q?Z，可取r = 0。若b 不整除a，考虑集合 A = { a ? kb；k?Z }, 在集合A中有无限多个正整数，设最小的正整数是r = a ? k0b，则必有0 r b，即(2)式成立. 否则就有r ? b。因为b ?a，所以r ? b。于是r b，即a ? k0b b，a ? k0b ? b 0，这样，在集合A中，又有正整数a ? k0b ? b r，这与r的最小性矛盾。所以式(2)必定成立。取q = ? k0知式(1)成立。存在性得证。 唯一性 假设有两对整数q ?，r ?与q ??，r ??都使得式(1)成立，即 a = q ??b ? r ?? = q ?b ? r ?，0 ? r ?, r ?? b， 则(q?? ? q ?)b = r ? ? r ??，|r ? ? r ??| b，因此 r ? ? r ?? = 0，r ? = r ??， 再由上式得出q ? = q ??，唯一性得证. 带余除法 定义1.3 称式(1)中的q是a被b除的商，r是a被b除的余数。 定义1.4 (2)式中的q称为a被b除得的不完全商, r称为a被b除所得的余数, 也叫做非负最小剩余, 常记作?a?b ? r.其中b常略去不写。以后总称除数b 0以及因数为正。 定义1.5 (2)式中若余数r 满足: ?b/2 ? r b/2, 称其为绝对最小剩余. 定理1.3 对于整数a1, a2, b, 其中b 0, 有: ?a1 ? a2?b ? ??a1?b ? ?a2?b?b , ?a1 ? a2?b ? ??a1?b ? ?a2?b?b , ?a1a2?b ? ??a1?b ?a2?b?b .