第6章整除.pptVIP

(2)17＝102－85 ＝102－(493－102·4)＝102·5－493 ＝(595－493) ·5－493＝595·5－493·6 ＝595·5－(3468－595·5)·6＝595·35－3468·6 ＝(24871－3468·7)·35－3468·6 ＝24871·35＋3468·(－251)。 定理6.13 设a和b是正整数，且(a，b)＝d，[a，b]＝m，则ab＝dm。 定理6.14 设a、b、c都是正整数，若a|bc，且(a，b)＝1，则a|c。 定理6.16 设a、b、c都是正整数，若a|c，b|c，且(a，b)＝1，则ab|c。 例2设f(x)＝a0xn＋a1xn－1＋…＋an－1x＋an是整系数多项式，如果10|f(2)且10|f(5)，则10|f(10)。 例3设m、n为自然数，mn|(m2＋n2)，则m＝n。 定理6.17 若p是素数，则p a当且仅当(p，a)＝1。 设(a，b2)＝u，(a，b1b2)＝v。则由(a，b2)＝u得u|a且u|b2，有u|a、u|b1b2，即u是a与b1b2的公因数，故u≤v。 定理6.19 设a1、a2、…、an都是正整数，且p是素数，若p|a1a2…an，则至少有一个ar使得p|ar，其中1≤r≤n。 定理6.20(算术基本定理)设正整数a＞1，则a＝p1p2…ps，其中p1、p2、…、ps都是素数，且若不计素因数的次序，其分解是惟一的。 若将a的分解式中相同的素因数合并为它的幂数，则a只能分解成一种形式：a＝ … ，s≥1，其中p1、p2、…、ps是互不相同的素数，、、…、是正整数。我们称a＝ … 为a的标准分解式。 推论1 设正整数a和b的标准分解式分别为： a＝ … ， b＝ … ，则 (a，b)＝ … ， ，1≤j≤s [a，b]＝ … ， ，1≤j≤s 推论2 设?(n)表示正整数n的所有正因数的个数。若a＝ … ， 则 * * 6.1 因数和倍数 6.2 素数和合数 6.4 最大公因数和最小公倍数 6.3 带余除法与辗转相除法 6.5 算术基本定理 6.1 因数和倍数 定义6.1 任给两个整数a和b，其中b≠0，若存在整数q使a＝bq，则称b整除a，记作b|a，此时把b叫做a的因数或约数，把a称为b的倍数。否则，就说b不整除a，记作b a。 若a＝bq，而b≠±a，b≠±1，则称b是a的真因数或真约数。 定理6.1(1)b|a?－b|a?b|－a?|b|||a|。 (2)若b|a且c|b，则c|a。 (3)c|a且c|b?c|(ma＋nb)，其中m、n∈Z。 (4)若b|a且a≠0，则|b|≤|a|，即非零整数仅有有限个因数。 (5)若m≠0，则b|a?mb|ma。 (6)若b|a且a|b，则a＝±b。 例1若3|n且7|n，则21|n。 证明 由3|n知存在整数m使n＝3m，所以7|3m。由此及7|7m得7|(7m－2·3m)，即7|m。因而有21|n。 例2若a＝2b－1，a|2n，则a|n。 证明 由a|2n得a|2bn，由a＝2b－1得n＝2bn－an，所以a|n。 6.2 素数和合数 定义6.2大于1且只有1和自身这两个正因数的正整数，称为素数或质数；大于1且不是素数的正整数称为合数。若正整数a有一个因数b，而b是素数，称b是a的素因数。 依据该定义，可以将所有的正整数分为三类：素数、合数和1。 定理6.2 a是大于1的合数，当且仅当存在整数b和c，使得a＝bc，其中，1＜b＜a，1＜c＜a。 证明 由合数的定义即得。 定理6.3 若a是大于1的整数，则其大于1的最小正因数p一定是素数。 证明 若a是素数，取p＝a，则结论成立。若a是合数，取p是a的大于1的最小正因数。若p是合数，则存在c且1＜c＜p，使得c|p。由c|p和p|a得c|a，因此，c是p的一个正因数，与p的选取矛盾。所以p是素数。 定理6.4 若a是大于1的整数，则a一定可以表示为素数的乘积，即a＝p1p2…ps，其中p1、p2、…、ps都是素数。 证明 若a