第二次课–整除与同余.pptVIP

最小公倍数与最大公约数关系 例9　a = 888，b = 312，求[a，b]． 解　(888，312) = 24，则[888，312] = =11544． 1.2 素数 定义1　如果一个大于1的整数p除?1和?p外 无其他因子，则p称为一个素数，否则称为 合数． 定理1　设p是一个素数，则 1）对任意整数a，如果p不整除a，则 (p，a) = 1． 2）如果p?ab，则p?a，或p?b． 1.2素数 证明: 　1）因为(p，a) ?p，由素数的定义，(p，a) = 1，或者(p，a) = p．因为p不整除a，所以(p，a) ?p．故(p，a) = 1． 2）如果p?a，则成立．否则(p，a) = 1，则由互素的性质，有p?b． 定理2 算术基本定理 每个大于1的整数a都可以分解为有限个素数的乘积： a = p1 p2…pr． 该分解除素数因子的排列外是唯一的． 证明: 　(1) 分解是显然的，只需证明分解除素数因子的排列外是唯一的． (2) 假设a有两个分解： a = p1p2…pr = q1q2…qs． 由于p1?q1q2…qs，则p1整除q1，q2，…，qs之一，不失一般性，假设p1?q1，由p1，q1都是素数得p1 = q1．在等式两边消去p1，q1，得 p2p3…pr = q2q3…qs． 重复上述过程可得p1p2…pr和q1q2…qs除排列外是相同的，证毕． 标准因子分解式 由于p1，p2，…，pr中可能存在重复，所以a的分解式可表示为有限个素数的幂的乘积： a =p1k1 p2k2… pmkm． 这称为a的标准因子分解式． 例1.2.2　2100的标准因子分解式： 2100 = 2?2?3? 5? 5?7 = 22?31?52 ? 71． 试分解n=32954765761773295963 Eratosthenes筛法 定理1.2.3　设a是任意大于1的整数，则a的除1外最小正因子q是一素数，并且当a是一合数时， 证明　由算术基本定理，该定理的前一点是显然的． 当a是一合数时，可设 a = a1q，其中a1?q， 则a = a1q ? q2， 定理证毕． 求不超过100的全部素数． 第1步　找出的全部素数：2，3，5，7． 第2步　在1～100中分别划去第1步找出的每个素数的全部倍数：分别划去2的全部倍数、3的全部倍数、5的全部倍数和7的全部倍数． （1）划去2的全部倍数： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Eratosthenes筛法 Eratosthenes筛法 得到剩下的数： 1 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 Eratosthenes筛法 （2）划去3的全部倍数：