1、第 11章 初等数论 1第 11章 初等数论 11.1 素数 11.2 最大公约数与最小公倍数 11.3 同余 11.4 一次同余方程与中国剩余定理 11.5 欧拉定理和费马小定理 211.1 素数 整除、倍数和因子 带余除法 素数与合数 算术基本定理 筛法3整除、倍数和因子今后只考虑正整数的正因子 .平凡因子 : 1和自身真因子 : 除 1和自身之外的因子例如 , 2, 3 是 6 的真因子设 a, b是两个整数，且 b0. 如果存在整数 c 使 a=bc， 则称 a 被 b 整除 ，或 b 整除 a， 记作 b|a. 此时 , 又称 a 是 b 的倍数 ， b是 a 的 因子 . 把 b
2、不整除 a 记作 b a.例如 , 6有 8个因子 1, 2, 3和 6.4整除的性质性质 11.1.1 若 a |b且 a |c, 则 x, y, 有 a | xb+yc.性质 11.1.2 若 a |b且 b |c, 则 a |c.性质 11.1.3 设 m0, 则 a |b 当且仅当 ma | mb.性质 11.1.4 若 a | b且 b | a, 则 a=b.性质 11.1.5 若 a | b且 b0, 则 |a|b|. 带余除法 : a=qb+r, 0r 1是合数当且仅当 a=bc, 其中 11, p是素数且 d | p, 则 d=p.性质 11.1.9 设 p是素数且 p | a
3、b, 则必有 p | a 或者 p | b. 设 p是素数且 p | a1a2 ak, 则必存在 1ik, 使得 p| ai.注意 :当 d不是素数时 ,d | ab不一定能推出 d | a或 d | b. 素数 (质数 ):大于 1且只能被 1和自身整除的正整数合数 : 大于 1且不是素数例如 , 2,3,5,7,11是素数 , 4,6,8,9是合数 . 6算术基本定理定理 11.1(算术基本定理 ) 设 a1, 则 a= , 其中 p1,p2, pk是不相同的素数 , r1,r2, rk是正整数 , 并且在不计顺序的情况下 , 该表示是惟一的 . 该表达式称作整数 a的素因子分解 . 例如
4、 30=2 3 5, 117=32 13, 1024=210 推论 设 a= , 其中 p1,p2, pk是不相同的素数 , r1,r2, rk是正整数 , 则正整数 d为 a的因子的充分必要条件是 d= , 其中 0siri, i=1,2, k.7例题例 1 21560有多少个正因子 ?解 21560=2357211由推论 , 21560的正因子的个数为 4232=48.例 2 10!的二进制表示中从最低位数起有多少个连续的 0?解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得 10!=2834527,故 10!的二进制表示中从最低位数起有 8个连续
5、的 0.8素数的分布梅森数 (Marin Mersenne): 2p1, 其中 p为素数 当 n是合数时 , 2n1一定是合数 ,2ab1=(2a1)(2a(b1)+2a(b2)+2 a+1).梅森数可能是素数 , 也可能是合数 : 221=3, 231=7, 251=31, 271=127都是素数 , 而 2111=2047=2389是合数 .到 2002年找到的最大梅森素数是 2134669171, 有 4百万位 . 定理 11.2 有无穷多个素数 .证 用反证法 . 假设只有有穷多个素数 , 设为 p1,p2, pn,令 m=p1p2p n+1. 显然 , pi m, 1in. 因此 , 要么 m本身是素数，要么存在大于 pn的素数整除 m, 矛盾 .9素数的分布 (续 )(n): 小于等于 n的素数个数 . 例如 (0)=(1)=0, (2)=1, (3)=(4)=2, (5)=3. n 103 104 105 106 107(n)n/ln n(n)n/ln n168 1229 9592 78498 664579145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.07110
